[DS] Time Complexity (시간 복잡도)

Time Complexity (시간 복잡도)

Time Complexity(시간 복잡도)란 알고리즘의 효율성을 판단하기 위한 지표로서, 프로그램이 수행되는데 걸리는 절대적인 시간이 아닌 알고리즘이 수행되는데 사용되는 연산들이 몇 번 이루어지는지 나타낸 상대적 지표이

cf) 알고리즘을 평가하는 지표는 시간 효율성을 나타내는 시간 복잡도와 메모리 효율성을 나타내는 공간 복잡도가 있다.

시간 복잡도 자체가 자료구조는 아니지만 제가 공부한 자료구조 책에서 시간 복잡도를 다루고 있었습니다.

자료구조를 선택할 때 시간 복잡도가 중요한 고려사항이 되기때문에 책에서 다룬 것 같습니다.

 

Big-O Notation

시간복잡도와 공간복잡도를 표현하는 표기법 중 가장 많이 사용되는 표기법

cf) 시간복잡도를 표현하는 표기법에는 Big-O, Big-Omega, Theta등이 있음

• Big-O Notation은 최악의 경우를 나타내는 상한 접근법 (최악의 경우 n번 계산 수행 : O(n))
• 아래와 같이 1부터 n까지를 더하는 알고리즘에서도 여러가지 알고리즘이 있을 수 있으며 이 알고리즘을 어떻게 구성하느냐에 따라서 시간복잡도 차이가 큼 (A : O(n), B : O(n^2), C : O(1))

Big-O Notation의 속성

Sorting Algorithm 비교 (시간 복잡도)

	최선	평균	최악
Bubble Sort	O(n)	O(n^2)	O(n^2)
Heap Sort	O(nlogn)	O(nlogn)	O(nlogn)
Insertion Sort	O(n)	O(n^2)	O(n^2)
Merge Sort	O(nlogn)	O(nlogn)	O(nlogn)
Quick Sort	O(nlogn)	O(nlogn)	O(n^2)
Selection Sort	O(n^2)	O(n^2)	O(n^2)
Shell Sort	O(n)	O(nlogn^2)	O(nlogn^2)
Smooth Sort	O(n)	O(nlogn)	O(nlogn)

Data Structure 비교

Data Stucture	Average Case			Worst Case
	Search	Insert	Delete	Search	Insert	Delete
Array	O(n)	O(n)	O(n)	O(n)	O(n)	O(n)
Sorted Array	O(logn)	O(n)	O(n)	O(logn)	O(n)	O(n)
Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Doubly Linked List	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Stack	O(n)	O(1)	O(1)	O(n)	O(1)	O(1)
Hash table	O(1)	O(1)	O(1)	O(n)	O(n)	O(n)
Binary Search Tree	O(logn)	O(logn)	O(logn)	O(n)	O(n)	O(n)
B-Tree	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)
Red-Black Tree	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)
AVL Tree	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)	O(logn)

Reference

Carrano-Data Structures and Abstractions with Java 3rd Edition

https://blog.chulgil.me/algorithm/