빅오(O, big-O) 란 입력값이 무한대로 향할때 함수의 상한을 설명하는 수학적 표기 방법
점근적 실행 시간(Asymptotic Running Time)를 표기할 때 가장 널리 쓰이는 수학적 표기법 중 하나, 여기서 점근적 실행시간이란 입력값 n 이 커질 때(무한대로 향할경우), lim 함수의 실행 시간의 추이를 의미, 이를 달리 말하면 시간복잡도(Time Complexity)라 할수 있고, 시간복잡도는 어떤 알고리즘을 수행하는데 걸리는 시간을 설명하는 계산 복잡도를 의미, 이 계산복잡도를 표기하는 대표적인 방법이 빅오 이다.
빅오 표기법의 종류
1) O(1) : 입력값이 아무리 커도 실행 시간을 일정
2) O(log n) : 여기서 부터 입력값에 따라 실행 시간이 영향을 받음, 그러나 로그는 매우 큰 입력값에도 영향을 크게 받지 않음으로 웬만한 n의 크기에 대해서 매우 견고(대표적으로 이진검색)
3) O(n) : 입력값 만큼 실행 시간에 영향을 받음, 알고리즘을 수행하는 데 걸리는 시간은 입력값에 비례, 이러한 알고리즘은 선형시간(Linea Time) 알고리즘이라함, 정렬되지 않은 리스트에서 최댓값 , 최솟값을 찾는 경우가 이에 해당, 이를 찾기 위해 적어도 한번 이상 입력값을 찾아봐야함
4) O(n log n) : 병합 정렬을 비롯한 대부분의 효율 좋은 정렬 알고리즘이 이에 해당
5) O(n^2) : 버블 정렬같은 비효율적인 정렬 알고리즘이 이에 해당
6) O(2^n) : 피보나치 수를 재귀로 계산하는 알고리즘 같은 경우가 이에 해당
7) O(n!) : 외판원문제를 브루트 포스로 풀이할 때 이에 해당
빅오 관계에 대한 간단한 코드
for n in range(1, 15+1):
print(n, n **2, 2**n)
# 출력값
# 1 1 2
# 2 4 4
# 3 9 8
# 4 16 16
# 5 25 32
# 6 36 64
# 7 49 128
# 8 64 256
# 9 81 512
# 10 100 1024
# 11 121 2048
# 12 144 4096
# 13 169 8192
# 14 196 16384
# 15 225 32768