DJ pupm this party

점근적 표기법  O, Ω, Θ

점근적 표기법이란? 

어떤 함수의 증가 양상을 다른 함수와의 비교로 표현하는 수론과 해석학의 방법이다. 

알고리즘의 복잡도를 단순화 할때나 무한급수의 뒷부분을 간소화 할때 쓰이는 방법이다. 

예시) n^3 + n^2 + n -1을 O, Ω, Θ로 표현을 해보자 

O빅오 

가장 높은 차수보다 같거나 높은 식을 뜻한다.

그러므로 O(n^3), O(n^5), O(n^100)이렇게 표현할 수 있다. 이것은 시간 복잡도를 재는 척도로 사용하게 된다. 

Ω빅오메가

가장 높은 차수보다 같거나 낮은 식을 뜻한다. 

Ω(n^3), Ω(n), Ω(logn)

Θ빅세타 

최고차항을 뜻한다. Θ(n3)

시간복잡도 : 연산의 횟수를 점근적 표기법을 통해 추산적으로 표현하는 것 

대입과 조건문의 시간 복잡도

대입과 조건문의 시간 복잡도는  O(1)의 연산을 수행한다. 

반목문에서의 시간 복잡도 

반복문은 경우에 따라서 시간 복잡도가 달라지게된다. O(n)

- for i 0...i <10 x+=1 print(x) 처럼 내부에 알려진 값이 들어오게되면 대입연산 한번에 O(1)이기에 O(1)의 연산이라는 것을 알 수 있다.

- 그러나 반복횟수가 불분명한 값이 들어오게 되면 내부복잡도 O(1)이 n번 수행하게 되므로 O(n)이된다. 

- 중첩 반복문의 경우에는 n번에 해당하는 반복이 n번 수행하게 되므로 O(n^2)으로 표현될 수 있다. 

재귀함수의 시간 복잡도

재귀함수는 반복문과 비슷한 구조를 가지고 있다. 특정 조건을 만족하면 변화된 값을 넣어 해당 함수를 다시 실행시킨다. 

결국 순환구조를 생각해보면서 시간 복잡도를 생각해보면 쉽게 구할 수 있다. 

공간복잡도 : 메모리에서 코드가 차지하고 있는 정도

사용하는 배열의 크기에 따라 대략 어느 정도의 메모리를 사용하는지를 미리 계산할 수 있어, 메모리 제한을 넘지 않는 코드인지를 확인해 볼 수 있다.