Big-O Notation
Big-O notation은 알고리즘의 복잡도나 성능을 표현하는 방식이다. 이는 절대적인 수치를 보여주는 것이 아니지만 이를 통해서 현재 작성할 프로그램의 알고리즘을 미리 살펴보고 적당한 알고리즘을 선택하는 데 도움을 준다.
- 특징
- 플랫폼에 독립적이다.
- 통계적인 기대치를 표현한다.
- 모든 종류의 입력 데이타 크기에 대한 실행성능을 보여준다.
- 실제 실행시간과는 차이가 있을 수가 있다.
- 사용할 라이브러리가 얼마나 자주 실행될 지에 대한 고려를 해보아야 한다. 10:90의 법칙을 생각할 때 10의 경우에는 별로 차이가 있지 않겠지만 90의 경우의 코드에서는 심각하게 검토를 해보아 야 한다.
Good | Fair | Poor | |
Searching
Algorithm | Data Structure | Time Complexity | Space Complexity | |||
Average | Worst | Worst | ||||
Graph of |V| vertices and |E| edges | - | O(|E| + |V|) | O(|V|) | |||
Graph of |V| vertices and |E| edges | - | O(|E| + |V|) | O(|V|) | |||
Sorted array of n elements | O(log(n)) | O(log(n)) | O(1) | |||
Array | O(n) | O(n) | O(1) | |||
Shortest path by Dijkstra, | Graph with |V| vertices and |E| edges | O((|V| + |E|) log |V|) | O((|V| + |E|) log |V|) | O(|V|) | ||
Shortest path by Dijkstra, | Graph with |V| vertices and |E| edges | O(|V|^2) | O(|V|^2) | O(|V|) | ||
Graph with |V| vertices and |E| edges | O(|V||E|) | O(|V||E|) | O(|V|) | |||
Sorting
Algorithm | Data Structure | Time Complexity | Worst Case Auxiliary Space Complexity | ||||
Best | Average | Worst | Worst | ||||
Array | O(n log(n)) | O(n log(n)) | O(n^2) | O(n) | |||
Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) | |||
Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) | |||
Array | O(n) | O(n^2) | O(n^2) | O(1) | |||
Array | O(n) | O(n^2) | O(n^2) | O(1) | |||
Array | O(n^2) | O(n^2) | O(n^2) | O(1) | |||
Array | O(n+k) | O(n+k) | O(n^2) | O(nk) | |||
Array | O(nk) | O(nk) | O(nk) | O(n+k) | |||
Data Structures
Data Structure | Time Complexity | Space Complexity | |||||||
Average | Worst | Worst | |||||||
Indexing | Search | Insertion | Deletion | Indexing | Search | Insertion | Deletion | ||
O(1) | O(n) | - | - | O(1) | O(n) | - | - | O(n) | |
O(1) | O(n) | O(n) | O(n) | O(1) | O(n) | O(n) | O(n) | O(n) | |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
O(n) | O(n) | O(1) | O(1) | O(n) | O(n) | O(1) | O(1) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n log(n)) | |
- | O(1) | O(1) | O(1) | - | O(n) | O(n) | O(n) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | O(n) | O(n) | O(n) | O(n) | |
- | O(log(n)) | O(log(n)) | O(log(n)) | - | O(n) | O(n) | O(n) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | |
- | O(log(n)) | O(log(n)) | O(log(n)) | - | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | |
O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(n) | |
Heaps
Heaps | Time Complexity | ||||||||
Heapify | Find Max | Extract Max | Increase Key | Insert | Delete | Merge | |||
- | O(1) | O(1) | O(n) | O(n) | O(1) | O(m+n) | |||
- | O(n) | O(n) | O(1) | O(1) | O(1) | O(1) | |||
O(n) | O(1) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(m+n) | |||
- | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | O(log(n)) | |||
- | O(1) | O(log(n))* | O(1)* | O(1) | O(log(n))* | O(1) | |||
Graphs
Node / Edge Management | Storage | Add Vertex | Add Edge | Remove Vertex | Remove Edge | Query |
O(|V|+|E|) | O(1) | O(1) | O(|V| + |E|) | O(|E|) | O(|V|) | |
O(|V|+|E|) | O(1) | O(1) | O(|E|) | O(|E|) | O(|E|) | |
O(|V|^2) | O(|V|^2) | O(1) | O(|V|^2) | O(1) | O(1) | |
O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|V| ⋅ |E|) | O(|E|) |