Data Structure
๐งฉ [Data Structure] ๋ก๊ทธ ์๊ฐ(logarithmic time)์ด๋?
๐ Intro.
-
๋ก๊ทธ ์๊ฐ(logarithmic time)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋ถ์ํ ๋ ์ฌ์ฉํ๋ ์ฉ์ด๋ก, ์ด๋ค ์๊ณ ๋ฆฌ์ฆ์ด๋ ์ฐ์ฐ์ด ์ํ๋ ๋ ์
๋ ฅ ํฌ๊ธฐ(N)์ ๋ฐ๋ผ ์์
์๊ฐ์ด ์
๋ ฅ ํฌ๊ธฐ์ ๋ก๊ทธ ๊ฐ์ ๋น๋กํ๋ ๊ฒฝ์ฐ๋ฅผ ์๋ฏธํฉ๋๋ค.
โ
1๏ธโฃ ๋ก๊ทธ ์๊ฐ์ ์ ์.
-
๋ก๊ทธ ์๊ฐ์ ์
๋ ฅ ํฌ๊ธฐ N์ด ์ฆ๊ฐํ๋๋ผ๋ ์ฐ์ฐ ์๊ฐ ์ฆ๊ฐ๊ฐ ๋งค์ฐ ๋๋ฆฐ ๊ฒฝ์ฐ๋ฅผ ๋ํ๋
๋๋ค.
- ์๊ฐ ๋ณต์ก๋๋ฅผ ํํํ ๋ O(log N)์ผ๋ก ๋ํ๋
๋๋ค.
โ
2๏ธโฃ ๋ก๊ทธ ์๊ฐ์ ์๋ฏธ.
- ๋ง์ฝ ์
๋ ฅ ํฌ๊ธฐ N์ด 2๋ฐฐ๋ก ๋์ด๋๋, ์ฐ์ฐ ์๊ฐ์ 1ํ ์ ๋๋ง ์ถ๊ฐ๋๋ ๋ฐฉ์์ผ๋ก ์ฆ๊ฐํฉ๋๋ค.
- ์ด๋ ๋ก๊ทธ(logarithm)์ ์ฑ์ง์ ๊ธฐ์ธํ๋ฉฐ, ํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ ํน์ง์
๋๋ค.
โ
3๏ธโฃ ๋ก๊ทธ ์๊ฐ์ ์์.
1๏ธโฃ ์ด์ง ํ์(Binary Search) - O(log N)
-
์ด์ง ํ์์ ์ ๋ ฌ๋ ๋ฐฐ์ด์์ ํน์ ๊ฐ์ ์ฐพ์ ๋ ์ฌ์ฉ๋ฉ๋๋ค.
- ๋ฐฐ์ด์ ์ ๋ฐ์ผ๋ก ๋๋๋ ๋ฐฉ์์ผ๋ก ํ์ํ๋ฏ๋ก, ์
๋ ฅ ํฌ๊ธฐ N์ ๋ํด ์๊ฐ ๋ณต์ก๋๋ O(log N)์
๋๋ค.
๐2๏ธโฃ ์์.
- ๋ฐฐ์ด ํฌ๊ธฐ: N = 16
- ๋น๊ต ํ์:
- ์ฒซ ๋ฒ์งธ ๋น๊ต โ ํฌ๊ธฐ 16 โ 8๋ก ์ค์ด๋ฆ.
- ๋ ๋ฒ์งธ ๋น๊ต โ ํฌ๊ธฐ 8 โ 4.
- ์ธ ๋ฒ์งธ ๋น๊ต โ ํฌ๊ธฐ 4 โ 2.
- ๋ค ๋ฒ์งธ ๋น๊ต โ ํฌ๊ธฐ 2 โ 1์์ ์ข
๋ฃ.
- ์ด ๋น๊ต ํ์: logโ(16) = 4
3๏ธโฃ B-Tree์ B+ Tree ๊ฒ์ - O(log N)
-
B-Tree์ B+ Tree๋ ๋ฐ์ดํฐ๋ฒ ์ด์ค์ ํ์ผ ์์คํ
์์ ์ฌ์ฉ๋๋ ํจ์จ์ ์ธ ๋ฐ์ดํฐ ๊ตฌ์กฐ์
๋๋ค.
- ํธ๋ฆฌ์ ๋์ด๊ฐ log์ ๋น๋กํ๋ฏ๋ก, ๊ฒ์๊ณผ ์ฝ์
/์ญ์ ์ฐ์ฐ ๋ชจ๋ O(log N)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๋๋ค.
๐4๏ธโฃ ์์.
- ๋ฐ์ดํฐ ๊ฐ์: N = 1,000
- B+ Tree์์ ์ต๋ 100๊ฐ์ ์์์ ๊ฐ์ง๋ค๋ฉด, ํธ๋ฆฌ์ ๋์ด๋ logโโ(1,000) = 3
- ๊ฒ์ ์๊ฐ์ 3๋จ๊ณ๋ง์ ์ํ๋ ๋ฐ์ดํฐ๋ฅผ ์ฐพ์ ์ ์์ต๋๋ค.
4๏ธโฃ ์ด๋ฒคํธ ์ฒ๋ฆฌ์ ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ.
-
Merge Sort์ ๊ฐ์ ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ์์๋ ๋ก๊ทธ ์๊ฐ์ด ๋ํ๋ฉ๋๋ค.
- ๋ฌธ์ ๋ฅผ ์ ๋ฐ์ผ๋ก ๋๋์ด ์ฌ๊ท์ ์ผ๋ก ์ฒ๋ฆฌํ๋ฏ๋ก, ๊น์ด๋ log N์ ๋น๋กํฉ๋๋ค.
- ๋ณํฉ ๊ณผ์ ์ ์๊ฐ์ O(N), ๋ฐ๋ผ์ ์ ์ฒด ์๊ฐ ๋ณต์ก๋๋ O(N log N)์
๋๋ค.
โ
4๏ธโฃ ๋ก๊ทธ ์๊ฐ์ ํน์ง.
1๏ธโฃ ํจ์จ์ฑ:
- ๋ก๊ทธ ์๊ฐ ๋ณต์ก๋๋ ๋๊ท๋ชจ ๋ฐ์ดํฐ๋ฅผ ์ฒ๋ฆฌํ ๋ ๋งค์ฐ ํจ์จ์ ์
๋๋ค.
- ๋ฐ์ดํฐ ํฌ๊ธฐ N์ด ๊ธฐํ๊ธ์์ ์ผ๋ก ์ฆ๊ฐํ๋๋ผ๋, ์์
์๊ฐ์ ๋๋ฆฌ๊ฒ ์ฆ๊ฐํฉ๋๋ค.
2๏ธโฃ ์ ์ฉ ์ฌ๋ก:
-
๊ฒ์ ์๊ณ ๋ฆฌ์ฆ : ์ด์ง ํ์(Binary Search), B-Tree, AVL Tree, Hash Table ๋ฑ.
-
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ : Merge Sort, Heap Sort ๋ฑ.
-
ํ์ผ ์์คํ
๋ฐ ๋ฐ์ดํฐ๋ฒ ์ด์ค : ์ธ๋ฑ์ค ๊ฒ์(B+ Tree).
3๏ธโฃ ๊ธฐ๋ณธ ์ํ:
- ๋ก๊ทธ ์๊ฐ์ logโ(N) ๋๋ logโโ(N) ๊ฐ์ ์ํ์ ๋ก๊ทธ ํจ์์ ์ฑ์ง์ ๊ธฐ์ดํฉ๋๋ค.
๐5๏ธโฃ ์ ๋ฆฌ
-
๋ก๊ทธ ์๊ฐ(logarithmic time)์ O(log N)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ์๋ฏธํ๋ฉฐ, ๋ฐ์ดํฐ ํฌ๊ธฐ๊ฐ ์ฆ๊ฐํด๋ ์ฐ์ฐ ์๊ฐ์ด ๋๋ฆฌ๊ฒ ์ฆ๊ฐํฉ๋๋ค.
- ์ด๋ ์ด์ง ํ์, ํธ๋ฆฌ ๊ธฐ๋ฐ ๊ตฌ์กฐ, ๋ถํ ์ ๋ณต ์๊ณ ๋ฆฌ์ฆ ๋ฑ์์ ๋ํ๋๋ ํจ์จ์ ์ธ ์๊ฐ ๋ณต์ก๋์
๋๋ค.