๋ฐ์ํ
Time Complexity (์๊ฐ ๋ณต์ก๋)
- ์ปดํจํฐ ํ๋ก๊ทธ๋จ์ ์ ๋ ฅ๊ฐ๊ณผ ์ฐ์ฐ ์ํ ์๊ฐ์ ์๊ด๊ด๊ณ๋ฅผ ๋ํ๋ด๋ ์ฒ๋
- ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ๊ฑธ๋ฆฌ๋ ์๊ฐ๊ณผ ์ ๋ ฅ์ ํจ์ ๊ด๊ณ
- ์๊ณ ๋ฆฌ์ฆ์ ๋ก์ง์ด ์ผ๋ง๋ ์ค๋ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋์ง ๋ํ๋ด๋ ๋ฐ ์ฌ์ฉ
- ์๊ณ ๋ฆฌ์ฆ์ ๋ก์ง์ ์ฝ๋๋ก ๊ตฌํํ ๋, ํจ์จ์ ์ผ๋ก ๊ตฌํํ๊ธฐ์ํด ๊ณ ๋ คํด์ผ ํจ
- ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ ๊ตฌํ: ์ ๋ ฅ๊ฐ์ด ์ปค์ง์ ๋ฐ๋ผ ์ฆ๊ฐํ๋ ์๊ฐ์ ๋น์จ์ ์ต์ํํ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌ์ฑ
- ์ฃผ๋ก ๋น -์ค ํ๊ธฐ๋ฒ์ ์ฌ์ฉํด ๋ํ๋
์๊ฐ ๋ณต์ก๋๋ฅผ ํ๊ธฐํ๋ ๋ฐฉ๋ฒ
- Big-O(Big-Oh, ๋น -์ค) ⇒ ์ํ ์ ๊ทผ, ์ต์ ์ ๊ฒฝ์ฐ์ ๋ํด ๋ํ๋ด๋ ๋ฐฉ๋ฒ
- Big-Ω(Big-Omega, ๋น -์ค๋ฉ๊ฐ) ⇒ ํํ ์ ๊ทผ, ์ต์ ์ ๊ฒฝ์ฐ์ ๋ํด ๋ํ๋ด๋ ๋ฐฉ๋ฒ
- Big-θ(Big-Theta, ๋น -์ธํ) ⇒ ๋น ์ค์ ๋น ์ค๋ฉ๊ฐ์ ๊ณตํต๋ถ๋ถ, ์ต์์ ์ต์ ์ ์ค๊ฐ์ธ ํ๊ท ์ ์ธ ๋ณต์ก๋
Big-O ํ๊ธฐ๋ฒ
- ์ ๋ ฅ ๋ฒ์ n์ ๊ธฐ์ค์ผ๋ก ํด์ ๋ก์ง์ด ๋ช ๋ฒ ๋ฐ๋ณต๋๋์ง ๋ํ๋ด๋ ํ๊ธฐ๋ฒ
- ‘์ ๋ ฅ๊ฐ์ ๋ณํ์ ๋ฐ๋ผ ์ฐ์ฐ์ ์คํํ ๋, ์ฐ์ฐ ํ์์ ๋นํด ์๊ฐ์ด ์ผ๋ง๋งํผ ๊ฑธ๋ฆฌ๋๊ฐ?’๋ฅผ ํ๊ธฐํ๋ ๋ฐฉ๋ฒ
Big-O ํ๊ธฐ๋ฒ์ ์ข ๋ฅ
- O(1)
- ์ผ์ ํ ๋ณต์ก๋(constant complexity)๋ผ๊ณ ํ๋ฉฐ, ์ ๋ ฅ๊ฐ์ด ์ฆ๊ฐํ๋๋ผ๋ ์๊ฐ์ด ๋์ด๋์ง ์์
- ์ ๋ ฅ๊ฐ์ ํฌ๊ธฐ์ ๊ด๊ณ์์ด, ์ฆ์ ์ถ๋ ฅ๊ฐ์ ์ป์ด๋ผ ์ ์์
- O(n)
- ์ ํ ๋ณต์ก๋(linear complexity)๋ผ๊ณ ๋ถ๋ฅด๋ฉฐ, ์ ๋ ฅ๊ฐ์ด ์ฆ๊ฐํจ์ ๋ฐ๋ผ ์๊ฐ ๋ํ ๊ฐ์ ๋น์จ๋ก ์ฆ๊ฐํ๋ ๊ฒ์ ์๋ฏธ
- ์ ๋ ฅ๊ฐ์ด ์ปค์ง๋ฉด ์ปค์ง์๋ก ๊ณ์(n ์์ ์๋ ์)์ ์๋ฏธ๊ฐ ์ ์ ์์ด์ง๊ธฐ ๋๋ฌธ์, ๊ฐ์ ๋น์จ๋ก ์ฆ๊ฐํ๊ณ ์๋ค๋ฉด 2๋ฐฐ๊ฐ ์๋ 5๋ฐฐ, 10๋ฐฐ๋ก ์ฆ๊ฐํ๋๋ผ๋ O(n)์ผ๋ก ํ๊ธฐ
- O(log n)
- ๋ก๊ทธ ๋ณต์ก๋(logarithmic complexity)๋ผ๊ณ ๋ถ๋ฅด๋ฉฐ, Big-Oํ๊ธฐ๋ฒ์ค O(1) ๋ค์์ผ๋ก ๋น ๋ฅธ ์๊ฐ ๋ณต์ก๋
- O(n2)
- 2์ฐจ ๋ณต์ก๋(quadratic complexity)๋ผ๊ณ ๋ถ๋ฅด๋ฉฐ, ์ ๋ ฅ๊ฐ์ด ์ฆ๊ฐํจ์ ๋ฐ๋ผ ์๊ฐ์ด n์ ์ ๊ณฑ์์ ๋น์จ๋ก ์ฆ๊ฐํ๋ ๊ฒ์ ์๋ฏธ
- n3๊ณผ n5 ๋ ๋ชจ๋ O(n2)๋ก ํ๊ธฐ
- O(2n)
- ๊ธฐํ๊ธ์์ ๋ณต์ก๋(exponential complexity)๋ผ๊ณ ๋ถ๋ฅด๋ฉฐ, Big-O ํ๊ธฐ๋ฒ ์ค ๊ฐ์ฅ ๋๋ฆฐ ์๊ฐ ๋ณต์ก๋
์๋ฃ๊ตฌ์กฐ์์์ ์๊ฐ ๋ณต์ก๋
์๋ฃ ๊ตฌ์กฐ์ ํ๊ท ์๊ฐ ๋ณต์ก๋
์๋ฃ ๊ตฌ์กฐ | ์ ๊ทผ | ํ์ | ์ฝ์ | ์ญ์ |
๋ฐฐ์ด (Array) | O(1) | O(n) | O(n) | O(n) |
์คํ (Stack) | O(n) | O(n) | O(1) | O(1) |
ํ (Queue) | O(n) | O(n) | O(1) | O(1) |
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Double Linked List) | O(n) | O(n) | O(1) | O(1) |
ํด์ ํ ์ด๋ธ (Hash Table) | O(1) | O(1) | O(1) | O(1) |
์ด์ง ํ์ ํธ๋ฆฌ (BST) | O(log n) | O(log n) | O(log n) | O(log n) |
AVL ํธ๋ฆฌ | O(log n) | O(log n) | O(log n) | O(log n) |
๋ ๋ ๋ธ๋ ํธ๋ฆฌ | O(log n) | O(log n) | O(log n) | O(log n) |
์๋ฃ ๊ตฌ์กฐ์ ์ต์ ์ ์๊ฐ ๋ณต์ก๋
์๋ฃ ๊ตฌ์กฐ | ์ ๊ทผ | ํ์ | ์ฝ์ | ์ญ์ |
๋ฐฐ์ด (Array) | O(1) | O(n) | O(n) | O(n) |
์คํ (Stack) | O(n) | O(n) | O(1) | O(1) |
ํ (Queue) | O(n) | O(n) | O(1) | O(1) |
์ด์ค ์ฐ๊ฒฐ ๋ฆฌ์คํธ (Double Linked List) | O(n) | O(n) | O(1) | O(1) |
ํด์ ํ ์ด๋ธ (Hash Table) | O(n) | O(n) | O(n) | O(n) |
์ด์ง ํ์ ํธ๋ฆฌ (BST) | O(n) | O(n) | O(n) | O(n) |
AVL ํธ๋ฆฌ | O(log n) | O(log n) | O(log n) | O(log n) |
๋ ๋ ๋ธ๋ ํธ๋ฆฌ | O(log n) | O(log n) | O(log n) | O(log n) |
๋ฐ์ํ
'๐ Computer Science > Data Structure' ์นดํ ๊ณ ๋ฆฌ์ ๋ค๋ฅธ ๊ธ
[์๋ฃ๊ตฌ์กฐ] ํธ๋ฆฌ(Tree) (0) | 2023.03.09 |
---|---|
[์๋ฃ๊ตฌ์กฐ] ๊ทธ๋ํ(Graph) (0) | 2023.03.08 |
[์๋ฃ๊ตฌ์กฐ] ํ(Queue) (0) | 2023.03.06 |
[์๋ฃ๊ตฌ์กฐ] ์คํ(Stack) (0) | 2023.02.14 |
[์๋ฃ๊ตฌ์กฐ] ์ฐ๊ฒฐ ๋ฆฌ์คํธ(Linked List) (0) | 2023.02.10 |