์๊ฐ ๋ณต์ก๋
Big-Ω(๋น -์ค๋ฉ๊ฐ) | ์ต์ ์ผ ๋ (best case)์ ์ฐ์ฐ ํ์๋ฅผ ๋ํ๋ธ ํ๊ธฐ๋ฒ |
Big-θ(๋น -์ธํ) | ๋ณดํต์ผ ๋ (average case)์ ์ฐ์ฐ ํ์๋ฅผ ๋ํ๋ธ ํ๊ธฐ๋ฒ |
Big-O(๋น -์ค) | ์ต์ ์ผ ๋ (worst case)์ ์ฐ์ฐ ํ์๋ฅผ ๋ํ๋ธ ํ๊ธฐ๋ฒ |
- ์ ์ธ ๊ฐ์ง ํ๊ธฐ๋ฒ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ๊ฐ ์ต์ , ์ค๊ฐ(ํ๊ท ), ์ต์ ์ ๊ฒฝ์ฐ์ ๋ํ์ฌ ๋ํ๋ด๋ ๋ฐฉ๋ฒ์ด๋ค.
๊ฐ์ฅ ์์ฃผ ์ฌ์ฉ๋๋ ํ๊ธฐ๋ฒโ๏ธ Big-O ํ๊ธฐ๋ฒ
- ๋น ์ค ํ๊ธฐ๋ฒ์ ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ๋ฏ๋ก, ํ๋ก๊ทธ๋จ์ด ์คํ๋๋ ๊ณผ์ ์์ ์์๋๋ ์ต์ ์ ์๊ฐ๊น์ง ๊ณ ๋ คํ ์ ์๊ธฐ ๋๋ฌธ์ด๋ค.
- “์ต์ํ ํน์ ์๊ฐ ์ด์์ด ๊ฑธ๋ฆฐ๋ค” ํน์ “์ด ์ ๋ ์๊ฐ์ด ๊ฑธ๋ฆฐ๋ค”๋ฅผ ๊ณ ๋ คํ๋ ๊ฒ๋ณด๋ค “์ด ์ ๋ ์๊ฐ๊น์ง ๊ฑธ๋ฆด ์ ์๋ค”๋ฅผ ๊ณ ๋ คํด์ผ ๊ทธ์ ๋ง๋ ๋์์ด ๊ฐ๋ฅํ๋ค.
์๊ฐ๋ณต์ก๋์์ ์ค์ํ๊ฒ ๋ณด๋๊ฒ์ ๊ฐ์ฅํฐ ์ํฅ์ ๋ฏธ์น๋ n์ ๋จ์์ด๋ค.
1 O(1) --> ์์
2n + 20 O(n) --> n์ด ๊ฐ์ฅ ํฐ์ํฅ์ ๋ฏธ์น๋ค.
3n^2 O(n^2) --> n^2์ด ๊ฐ์ฅ ํฐ์ํฅ์ ๋ฏธ์น๋ค.
O(1) – ์์ ์๊ฐ : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋๋ฐ ์ค์ง ํ ๋จ๊ณ๋ง ์ฒ๋ฆฌํจ.
O(log n) – ๋ก๊ทธ ์๊ฐ : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋๋ฐ ํ์ํ ๋จ๊ณ๋ค์ด ์ฐ์ฐ๋ง๋ค ํน์ ์์ธ์ ์ํด ์ค์ด๋ฌ.
O(n) – ์ง์ ์ ์๊ฐ : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋จ๊ณ์ ์์ ์ ๋ ฅ๊ฐ n์ด 1:1 ๊ด๊ณ๋ฅผ ๊ฐ์ง.
O(n log n) : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋จ๊ณ์ ์๊ฐ N*(log2N) ๋ฒ๋งํผ์ ์ํ์๊ฐ์ ๊ฐ์ง๋ค. (์ ํ๋ก๊ทธํ)
O(n^2) – 2์ฐจ ์๊ฐ : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋จ๊ณ์ ์๋ ์ ๋ ฅ๊ฐ n์ ์ ๊ณฑ.
O(C^n) – ์ง์ ์๊ฐ : ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๊ธฐ ์ํ ๋จ๊ณ์ ์๋ ์ฃผ์ด์ง ์์๊ฐ C ์ n ์ ๊ณฑ.
์๊ฐ ๋ณต์ก๋ ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ ๊ฒฝ์ฐ
- ๊ฒฐ๊ณผ๋ฅผ ๋ฐํํ๋ ๋ฐ ์ต์ ์ ๊ฒฝ์ฐ 1์ด, ํ๊ท ์ ์ผ๋ก 1๋ถ, ์ต์ ์ ๊ฒฝ์ฐ 1์๊ฐ์ด ๊ฑธ๋ฆฌ๋ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ๊ณ , ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ๋ค๊ณ ๊ฐ์ ํ๊ฒ ๋ค.
- ์ด ์๊ณ ๋ฆฌ์ฆ์ 100๋ฒ ์คํํ๋ค๋ฉด, ์ต์ ์ ๊ฒฝ์ฐ 100์ด๊ฐ ๊ฑธ๋ฆฐ๋ค.
- ๋ง์ฝ ์ค์ ๋ก ๊ฑธ๋ฆฐ ์๊ฐ์ด 1์๊ฐ์ ํ์ฉ ๋๊ฒผ๋ค๋ฉด, ‘์ด๋์์ ๋ฌธ์ ๊ฐ ๋ฐ์ํ ๊ฑฐ์ง?’๋ ์๋ฌธ์ด ์๊ธด๋ค.
- ์ต์ ์ ๊ฒฝ์ฐ๋ง ๊ณ ๋ คํ์์ผ๋, ์ด๋์์ ๋ฌธ์ ๊ฐ ๋ฐ์ํ๋์ง ์์๋ด๊ธฐ ์ํด์๋ ๋ก์ง์ ๋ง์ ๋ถ๋ถ์ ํ์ ํด์ผ ํ๋ฏ๋ก ๋ฌธ์ ๋ฅผ ํ์ ํ๋ ๋ฐ ๋ง์ ์๊ฐ์ด ํ์ํ๋ค.
์๊ฐ ๋ณต์ก๋ ์ค๊ฐ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ ๊ฒฝ์ฐ
- ํ๊ท ๊ฐ์ ๊ธฐ๋ํ๋ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ณ ๋ คํ๋ค๋ฉด ์ด๋จ๊น?
- ์๊ณ ๋ฆฌ์ฆ์ 100๋ฒ ์คํํ ๋ 100๋ถ์ ์๊ฐ์ด ์์๋๋ค๊ณ ์๊ฐํ๋๋ฐ, ์ต์ ์ ๊ฒฝ์ฐ๊ฐ ๋ช ๊ฐ ๋ฐ์ํ์ฌ 300๋ถ์ด ๋๊ฒ ๊ฑธ๋ ธ๋ค๋ฉด ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ ๊ฒ๊ณผ ๊ฐ์ ๊ณ ๋ฏผ์ ํ๊ฒ ๋๋ค.
์๊ฐ ๋ณต์ก๋ ์ต์ ์ ๊ฒฝ์ฐ๋ฅผ ๊ณ ๋ คํ ๊ฒฝ์ฐ
- ๊ทน๋จ์ ์ธ ์์ด์ง๋ง, ์์ ๊ฐ์ด ์ต์ ์ ๊ฒฝ์ฐ๊ฐ ๋ฐ์ํ์ง ์๊ธฐ๋ฅผ ๋ฐ๋ผ๋ฉฐ ์๊ฐ์ ๊ณ์ฐํ๋ ๊ฒ๋ณด๋ค๋ ‘์ต์ ์ ๊ฒฝ์ฐ๋ ๊ณ ๋ คํ์ฌ ๋๋น’ํ๋ ๊ฒ์ด ๋ฐ๋์งํ๋ค.
- ๋ฐ๋ผ์ ๋ค๋ฅธ ํ๊ธฐ๋ฒ๋ณด๋ค Big-O ํ๊ธฐ๋ฒ์ ๋ง์ด ์ฌ์ฉํ๋ค.
- Big-O ํ๊ธฐ๋ฒ์ ‘์ ๋ ฅ๊ฐ์ ๋ณํ์ ๋ฐ๋ผ ์ฐ์ฐ์ ์คํํ ๋, ์ฐ์ฐ ํ์์ ๋นํด ์๊ฐ์ด ์ผ๋ง๋งํผ ๊ฑธ๋ฆฌ๋๊ฐ?’๋ฅผ ํ๊ธฐํ๋ ๋ฐฉ๋ฒ์ด๋ค.
O(1) : ์์
์๋ ์์ ์ฒ๋ผ ์ ๋ ฅ์ ๊ด๊ณ์์ด ๋ณต์ก๋๋ ๋์ผํ๊ฒ ์ ์ง๋๋ค.
def hello_world():
print("hello, world!")
O(N) : ์ ํ
์ ๋ ฅ์ด ์ฆ๊ฐํ๋ฉด ์ฒ๋ฆฌ ์๊ฐ๋๋ ๋ฉ๋ชจ๋ฆฌ ์ฌ์ฉ์ด ์ ํ์ ์ผ๋ก ์ฆ๊ฐํ๋ค.
def print_each(li):
for item in li:
print(item)
O(N^2) : Square
๋ฐ๋ณต๋ฌธ์ด ๋๋ฒ ์๋ ์ผ์ด์ค
def print_each_n_times(li):
for n in li:
for m in li:
print(n,m)
O(log n) O(n log n)
์ฃผ๋ก ์
๋ ฅ ํฌ๊ธฐ์ ๋ฐ๋ผ ์ฒ๋ฆฌ ์๊ฐ์ด ์ฆ๊ฐํ๋ ์ ๋ ฌ์๊ณ ๋ฆฌ์ฆ์์ ๋ง์ด ์ฌ์ฉ๋๋ค.
๋ค์์ ์ด์ง๊ฒ์์ ์์ด๋ค.
def binary_search(li, item, first=0, last=None):
if not last:
last = len(li)
midpoint = (last - first) / 2 + first
if li[midpoint] == item:
return midpoint
elif li[midpoint] > item:
return binary_search(li, item, first, midpoint)
else:
return binary_search(li, item, midpoint, last)
์๊ฐ๋ณต์ก๋๋ฅผ ๊ตฌํ๋ ์๋ น
๊ฐ ๋ฌธ์ ์ ์๊ฐ๋ณต์ก๋ ์ ํ์ ๋นจ๋ฆฌ ํ์ ํ ์ ์๋๋ก ์๋ ์๋ฅผ ํตํด ๋น ๋ฅด๊ฒ ์์ ๋ณผ์ ์๋ค.
- ํ๋์ ๋ฃจํ๋ฅผ ์ฌ์ฉํ์ฌ ๋จ์ผ ์์ ์งํฉ์ ๋ฐ๋ณต ํ๋ ๊ฒฝ์ฐ : O (n)
- ์ปฌ๋ ์ ์ ์ ๋ฐ ์ด์ ์ ๋ฐ๋ณต ํ๋ ๊ฒฝ์ฐ : O (n / 2) -> O (n)
- ๋ ๊ฐ์ ๋ค๋ฅธ ๋ฃจํ๋ฅผ ์ฌ์ฉํ์ฌ ๋ ๊ฐ์ ๊ฐ๋ณ ์ฝ๋ ์ ์ ๋ฐ๋ณต ํ ๊ฒฝ์ฐ : O (n + m) -> O (n)
- ๋ ๊ฐ์ ์ค์ฒฉ ๋ฃจํ๋ฅผ ์ฌ์ฉํ์ฌ ๋จ์ผ ์ปฌ๋ ์ ์ ๋ฐ๋ณตํ๋ ๊ฒฝ์ฐ : O (n²)
- ๋ ๊ฐ์ ์ค์ฒฉ ๋ฃจํ๋ฅผ ์ฌ์ฉํ์ฌ ๋ ๊ฐ์ ๋ค๋ฅธ ์ฝ๋ ์ ์ ๋ฐ๋ณต ํ ๊ฒฝ์ฐ : O (n * m) -> O (n²)
- ์ปฌ๋ ์ ์ ๋ ฌ์ ์ฌ์ฉํ๋ ๊ฒฝ์ฐ : O(n*log(n))
๊ณต๊ฐ ๋ณต์ก๋
๊ณต๊ฐ ๋ณต์ก๋๋ ์๊ฐ ๋ณต์ก๋์ ์ ์ฌํ๊ฒ ๋น ์ค ํ๊ธฐ๋ฒ์ ์ฌ์ฉํฉ๋๋ค.
๋ค์ ์๊ณ ๋ฆฌ์ฆ์ ๋ณด๊ณ ๊ณต๊ฐ ๋ณต์ก๋๋ฅผ ๊ณ์ฐํด ๋ณด๊ฒ ์ต๋๋ค.
int sum(int a[], int n)
{
int x = 0;
for(int i = 0; i < n; i++) {
x = x + a[i];
}
return(x);
}
์ ์๊ณ ๋ฆฌ์ฆ์ 4๊ฐ์ ๋ณ์๋ฅผ ์ฌ์ฉํ๊ณ ์์ต๋๋ค.
- int arr[n] : 4*n byte (์ ๋ ฅ ๊ณต๊ฐ)
- int n : 4 byte (์ ๋ ฅ ๊ณต๊ฐ)
- int x : 4 byte (๋ณด์กฐ ๊ณต๊ฐ)
- int i : 4 byte (๋ณด์กฐ ๊ณต๊ฐ)
์ด 4n+12 ์ ๋ฉ๋ชจ๋ฆฌ๋ฅผ ์๊ตฌํฉ๋๋ค. ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ ๋ ฅ ๊ฐ์ ๋ฐ๋ผ ์ ํ์ ์ผ๋ก ์ฆ๊ฐํ๊ธฐ ๋๋ฌธ์ ๊ณต๊ฐ ๋ณต์ก๋๋ O(n)์ด ๋ฉ๋๋ค.
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ๋น๊ต
Sorting Algorithms | ๊ณต๊ฐ ๋ณต์ก๋ | ์๊ฐ ๋ณต์ก๋ | ||
์ต์ | ์ต์ | ํ๊ท | ์ต์ | |
Bubble Sort | O(1) | O(n) | O(n2) | O(n2) |
Heapsort | O(1) | O(n log n) | O(n log n) | O(n log n) |
Insertion Sort | O(1) | O(n) | O(n2) | O(n2) |
Mergesort | O(n) | O(n log n) | O(n log n) | O(n log n) |
Quicksort | O(log n) | O(n log n) | O(n log n) | O(n2) |
Selection Sort | O(1) | O(n2) | O(n2) | O(n2) |
Shell Sort | O(1) | O(n) | O(n log n2) | O(n log n2) |
Smooth Sort | O(1) | O(n) | O(n log n) | O(n log n) |
์๋ฃ๊ตฌ์กฐ ๋น๊ต
Data Structures | Average Case | Worst Case | ||||
Search | Insert | Delete | Search | Insert | Delete | |
Array | O(n) | N/A | N/A | O(n) | N/A | N/A |
Sorted Array | O(log n) | O(n) | O(n) | O(log n) | 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(log n) | O(log n) | O(log n) | O(n) | O(n) | O(n) |
B-Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
Red-Black tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |
AVL Tree | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) | O(log n) |