빅오표기법과 복잡도

https://www.boostcourse.org/cs204/lecture/480344/?isDesc=false

자바로 구현하고 배우는 자료구조

위 강의를 보고 정리한 내용~

내가 빅오표기법이나 복잡도를 이해할 때 이 강의가 가장 도움이 되었기 때문에 공유함

 

규칙1. input ≥ 0 (입력값은 항상 0보다 크다. 복잡도는 항상 0보다 크다)

규칙2. functions do more work for more input (더 많은 입력값이 있으면 더 많은 작업이 필요하다)

규칙3. drop all constants 상수는 고려하지 않음. (3n, 5n, 10n ⇒ 모두 n 임)

규칙4. ignore lower order terms 낮은 차수의 항을 무시함 (n^3 + n^2 + n 같은게 있으면 n^3만 고려함)

규칙5. ignore the base of logs 로그의 밑을 무시함. 모든 로그는 서로 배수관계이므로 복잡도에 대해 얘기할 때 로그의 밑은 무시해도 된다

규칙6. 2n = O(n) ⇒ 2n이 어떤 함수의 집합(O(n))에 속함 (등호 : 집합에 속한다는 뜻)

 

알고리즘에서 1보다 작은 값은 고려하지 않음.. 무한으로 커졌을 때를 고려함(최대값)

 

빅오표기법

Big O Notation (* O = Ordnung *질서라는 뜻의 독어)

 

o 작은 오: 빠르지만 같지는 않음 : faster

O 빅오복잡도(big o complexity) : 어떤 알고리즘이 비교하고자 하는 다른 알고리즘과 같거나 더 빠른 것 : same or faster

θ  세타 : 알고리즘이 같은 정도로 증가함 : same rate

Ω 빅오메가복잡도(big omega complexity): 같거나 더 느린 알고리즘 : same or slower

ω 리틀오메가복잡도 : 더 느리지만 같지 않음 : slower

 

n^2 는 O (n^3)으로 표기할 수 있음

O 는 '최악의 경우 이 정도'라는 의미로 더 자주 쓰이고, o는 '이것보단 확실히 빠르다'는 의미로 쓰인다

2^n= ω (n) 얘도 이렇게 쓸 수 있는거 맞고

3n^3+4n^2+5n+6 = θ ( n^3) 얘도 이렇게 쓸 수 있는거 맞음

 

위 그래프의 어디 범위에 속하느냐로 표기법을 파악할 수 있다.

강의를 천천히 따라가면 더 이해하기 쉬울 듯