⏱시간 복잡도: Big O 표기법

⏳ 알고리즘 성능 표기법

Big O(빅-오) 표기법 : O(N)

• 가장 많이, 일반적으로 사용함
• 알고리즘 최악의 실행 시간을 표기
• 즉, 아무리 최악의 상황이더라도 이정도의 성능은 보장한다는 의미

오메가 표기법 : Ω(N)

• 알고리즘 최상의 실행 시간을 표기

세타 표기법 : Θ(N)

• 알고리즘 평균 실행 시간을 표기

---

⏳ Big O 표기법

• 입력 $N$에 따라 결정되는 시간 복잡도 함수이다.
• 입력 $N$에 따라 시간 복잡도가 기하급수적으로 늘어날 수 있다.
• 입력 $N$에 따라 몇 번 실행이 되는 지를 계산하면 된다.
• $O(1), O(log n), O(n), O(nlog n), O(n^2), O(2^n), O(n!)$

• $O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!)$
• 참고: $log N$의 밑은 $2$이다. $(log_2 N)$

1. $O(1) : N$에 상관 없이 무조건 상수번 실행하는 경우

if n > 10:
    print(n)

2. $O(N) : N$에 따라 $aN + b$번 실행하는 경우

variable = 1
for num in range(3):
    for index in range(n):
        print(index)

3. $O(N^2) : N$에 따라 $aN^2 + bN + c$번 실행하는 경우

variable = 1
for i in range(300):
    for num in range(n):
    	for indec in range(n):
        	print(n)

---

앞으로 알고리즘을 배우면서 계속 추가할 예정임