-
Big-O NotationC++ 2014. 3. 20. 04:38
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,
using a Min-heap as priority queueGraph with |V| vertices and |E| edges
O((|V| + |E|) log |V|)
O((|V| + |E|) log |V|)
O(|V|)
Shortest path by Dijkstra,
using an unsorted array as priority queueGraph 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|)
'C++' 카테고리의 다른 글
Structured Paradigms 과 Object paradigm (0) 2014.03.20 Volitile Keyword (0) 2014.03.09 Object Pool (0) 2014.03.09 Dynamic Memory Allocation and Memory Leak (0) 2014.03.02 Rvalue reference (우측값 참조) (0) 2014.02.28