Home > Data Structure > ๐Ÿงฉ [Data Structure] ๋กœ๊ทธ ์‹œ๊ฐ„(logarithmic time)์ด๋ž€?

๐Ÿงฉ [Data Structure] ๋กœ๊ทธ ์‹œ๊ฐ„(logarithmic time)์ด๋ž€?
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)์˜ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ์˜๋ฏธํ•˜๋ฉฐ, ๋ฐ์ดํ„ฐ ํฌ๊ธฐ๊ฐ€ ์ฆ๊ฐ€ํ•ด๋„ ์—ฐ์‚ฐ ์‹œ๊ฐ„์ด ๋А๋ฆฌ๊ฒŒ ์ฆ๊ฐ€ํ•ฉ๋‹ˆ๋‹ค.
    • ์ด๋Š” ์ด์ง„ ํƒ์ƒ‰, ํŠธ๋ฆฌ ๊ธฐ๋ฐ˜ ๊ตฌ์กฐ, ๋ถ„ํ•  ์ •๋ณต ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋“ฑ์—์„œ ๋‚˜ํƒ€๋‚˜๋Š” ํšจ์œจ์ ์ธ ์‹œ๊ฐ„ ๋ณต์žก๋„์ž…๋‹ˆ๋‹ค.