빅오 표기법

                   -Intro to Big O
                   -Timing Our Code
                   -Counting Operations
                   -Official Intro to Big O 
                   -Simplifying Big O Expressions
                   -Space Complexity
                   -Logs 

빅오 소개

Big O를 사용하면 일부 코드가 얼마나 빠르고 효율적인지 결정할 수 있습니다.

문제에 대한 솔루션을 프로그래밍하는 방법에는 여러 가지가 있습니다. 그러나 일부 방법은 문제를 해결하는 데 다른 방법보다 빠릅니다. Big O를 사용하면 코드를 다른 코드와 비교하여 최상의 성능을 얻을 수 있습니다.

Big O 표기법은 3가지 범주로 나눌 수 있습니다.
O(1)은 항상 3개의 연산입니다.

 function addUpTo(n) {
 return n * (n + 1) / 2; 
 }

O(n)은 n(10n)의 배수로 제한되는 작업 수입니다.

function addUpTo(n) {
let total = 0; 
for (let i = 1; i <= n; i++) {
total += i; 
 }
return total; 
}

O(n^2)는 다른 작업 내부의 작업입니다.

function printAllPairs(n) {
  for (var i = 0; i < n; i++) {
   for (var j = 0; j < n; j++) {
     console.log(i,j);
   }
 }
}

코드 타이밍

좋은 코드는 속도와 효율성에 최적화되어 있습니다. 불필요하게 부풀려진 코드가 있을 수 있습니다. 불필요한 코드는 응용 프로그램이 느려 보일 수 있음을 의미할 수 있습니다. 코드가 느려지거나 충돌할 때 코드에서 비효율적인 부분을 식별하면 접근 방식에서 문제점을 찾는 데 도움이 될 수 있습니다.

계산 작업

초를 세는 대신 컴퓨터가 수행해야 하는 간단한 작업의 수를 세십시오.

계산에 따라 작업 수는 2n만큼 낮거나 5n + 2만큼 높을 수 있습니다.

그러나 정확한 수에 관계없이 연산 수는 대략 n에 비례하여 증가합니다.

Big O 공식 소개

Big O 표기법은 퍼지 계산을 공식화하는 방법입니다. 알고리즘의 런타임에 대해 공식적으로 이야기할 수 있습니다.
입력이 증가함에 따라 증가합니다.

함수에 대한 입력 사이의 관계 또는 입력이 증가함에 따라 해당 함수의 런타임이 어떻게 변경되는지 설명합니다.

입력 크기와 해당 입력 크기에 상대적인 시간 및 해당 입력에 상대적인 시간 간의 관계입니다.

컴퓨터가 수행해야 하는 간단한 작업의 수가 n이 증가함에 따라 궁극적으로 일정 시간 f(n)보다 적은 경우 알고리즘은 o(f(n))라고 합니다.

f(n)은 선형일 수 있습니다(f(n) = n)
f(n)은 2차일 수 있습니다(f(n) = n^2)
f(n)은 일정할 수 있습니다(f(n) = 1)
f(n)은 뭔가 다를 수 있습니다

Big O 표현식 단순화

Big O로 복잡성을 분석하는 것은 복잡해질 수 있습니다. 규칙이 항상 작동하는 것은 아니지만 유용한 출발점입니다.

산술 연산은 상수입니다.

변수 할당이 일정함

배열(인덱스 기준) 또는 객체(키 기준)의 요소 액세스가 일정함

루프에서 복잡성은 루프의 길이에 루프 내부에서 발생하는 모든 것의 복잡성을 곱한 것입니다.

공간 복잡성

지금까지 우리는 시간 복잡도에 초점을 맞추었습니다. 입력의 크기가 증가함에 따라 알고리즘의 런타임을 어떻게 분석할 수 있습니까?

이제 입력 크기가 증가함에 따라 알고리즘이 차지하는 공간에 어떤 일이 발생하는지 집중해 보겠습니다.

Big O 표기법을 사용하여 공간 복잡성을 분석할 수도 있습니다.

알고리즘에서 코드를 실행하려면 얼마나 많은 추가 메모리를 할당해야 합니까?

보조 공간 복잡도는 입력이 차지하는 공간을 포함하지 않고 알고리즘에 필요한 공간을 나타냅니다.

공간 복잡성에 대한 규칙

대부분의 프리미티브(부울, 숫자, 정의되지 않음, 널)는 상수 공간입니다.

문자열에는 O(n) 공백이 필요합니다(여기서 n은 문자열 길이).

참조 유형은 O(n)입니다. 여기서 n은 길이(배열의 경우) 또는 키의 수(객체의 경우)입니다.

로그

특정 검색 알고리즘에는 로그 시간 복잡도가 있습니다. 효율적인 정렬 알고리즘에는 로그가 포함됩니다. 재귀는 때때로 로그 공간 복잡성을 포함합니다.