[ 복잡도 ] 정렬 알고리즘의 복잡도

 

 

정렬 알고리즘에 따른 복잡도

 

Algorithms	space complexity	time complexity
	최악	최선	평균	최악
bubble	O(1)	O(n)	O(n^2)	O(n^2)
heap	O(1)	O(n log n)	O(n log n)	O(log n)
insertion	O(1)	O(n n)	O(n^2)	O(n^2)
merge	O(n)	O(n log n)	O(n log n)	O(log n)
quick	O(log n)	O(n log n)	O(n log n)	O(n^2)
selection	O(1)	O(n^2)	O(n^2)	O(n^2)
shell	O(1)	O(n)	O(n^1.25)	O(n^1.25)
smooth	O(1)	O(n)	O(n log n)	O(n log n)

 

 

 

자료 구조 별 시간 복잡도 Big-O

 

Data Structures	Search	Insert	Delete
Array	O(n)	N/A	N/A
Sorted Array	O(log n)	O(n)
Linked List	O(n)	O(1)
Doubly Linked List
Stack
Hash Table	O(n)
Binary Search Tree
B-Three	O(log n)
Red-Black Tree
AVL Tree