: 입력값이 무한대로 향할 때 함수의 상한을 설명하는 수학적 표기 방법
-
알고리즘: 실행 시간 (시간 복잡도) & 공간 요구사항 (공간 복잡도)
-
시간 복잡도: 어떤 알고리즘을 수행하는 데 걸리는 시간을 설명하는 계산 복잡도
-
점근적 실행 시간 (Asymptotic Running Time)
종류
최고차항만 표기, 계수 무시
입력값에 따른 알고리즘의 실행 시간의 추이
O(1) 상수함수
: 입력값이 아무리 커도 실행시간이 일정 / 최고의 알고리즘
상수값이 상상을 넘어설 정도로 매우 크다면 사실상 의미X
ex) 해시 테이블의 조회 및 삽입, Stack push/pop
O(log n) 로그함수
: 입력값에 영향을 받음
but 로그는 매우 큰 입력값에도 크게 영향을 받지 않는 편
=> 웬만한 n 에 대해 견고함
ex) Binary Search Tree
O(n) 선형함수
: 입력값만큼 영향을 받음 / 시간과 입력값이 비례
선형 시간 알고리즘 (Linear-Time)
모든 입력값을 적어도 한 번 이상 확인함
ex) 정렬되지 않은 리스트에서 최대/최소 찾기, for 문
O(n log n)
: 대부분의 효율 좋은 정렬 알고리즘
ex) 병합 정렬, 퀵 정렬, 힙 정렬
TimSort
: Merge Sort + Insert SortPython (2.3 버전 이후) 표준 정렬 알고리즘으로 Timsort 사용
표준 정렬 알고리즘: .sort() =>length <= 10이면O(n), 그 외는O(n log n)Merge sort의 최악 시간 복잡도 & Insert Sort의 최고 시간 복잡도
(Merge:O(n log n), Insert Best:O(n))
=> 최고O(n)~ 최악O(n log n)
O(n^2) 다항함수
: 비효율적인 정렬 알고리즘
ex) 이중 for 문, 버블 정렬, 삽입 정렬, 선택 정렬
cf) m < n 일 경우는 O(mn)
O(2^n) 지수함수
: 재귀로 계산하는 알고리즘
ex) 피보나치 수열
cf) n^2 보다 훨씬 크다
O(n!)
: 가장 느린 알고리즘
입력값이 조금만 커져도 계산이 어려움
ex) TSP 문제의 Brute Force 풀이
-
가능한 가장 작은 notation을 사용
=>O(n^2)도 되고O(n)도 된다면 가장 작은O(n)을 사용 -
for i in range(0, n-constant)여도O(n)으로
대부분 시간과 공간이 트레이드오프 관계 (Space-Time Tradeoff)
: 실행 시간이 빠른 알고리즘은 공간을 많이 사용하고,
공간을 적게 차지하는 알고리즘은 실행 시간이 느리다.
빅오 - 상한, 빅오메가 - 하한, 빅세타 - 평균
분할 상환 분석 (Amortized Analysis)
ex) O(1) O(n) O(1) O(1) O(1) O(1) O(1) ...
=> 가끔 일어나는 O(n) 때문에 전체 시간 복잡도는 O(n) 이 됨
분할 상환 분석으로 하면 시간 복잡도는 Amortized O(1)
가끔 일어나는 최악의 시간을 알고리즘의 복잡도라고 하지 X
병렬화가 가능하면 더 우수한 알고리즘
참고:
파이썬 알고리즘 인터뷰
https://holika.tistory.com/entry/자료구조-빅오-표기법Big-O-notation이란 [Uing? Uing!!]
