๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ
๐Ÿ“š Computer Science/Data Structure

[์ž๋ฃŒ๊ตฌ์กฐ] Time Complexity (์‹œ๊ฐ„ ๋ณต์žก๋„)

by hyebin (Helia) 2023. 3. 7.
๋ฐ˜์‘ํ˜•

Time Complexity (์‹œ๊ฐ„ ๋ณต์žก๋„)

  • ์ปดํ“จํ„ฐ ํ”„๋กœ๊ทธ๋žจ์˜ ์ž…๋ ฅ๊ฐ’๊ณผ ์—ฐ์‚ฐ ์ˆ˜ํ–‰ ์‹œ๊ฐ„์˜ ์ƒ๊ด€๊ด€๊ณ„๋ฅผ ๋‚˜ํƒ€๋‚ด๋Š” ์ฒ™๋„
  • ๋ฌธ์ œ๋ฅผ ํ•ด๊ฒฐํ•˜๋Š” ๋ฐ ๊ฑธ๋ฆฌ๋Š” ์‹œ๊ฐ„๊ณผ ์ž…๋ ฅ์˜ ํ•จ์ˆ˜ ๊ด€๊ณ„
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋กœ์ง์ด ์–ผ๋งˆ๋‚˜ ์˜ค๋žœ ์‹œ๊ฐ„์ด ๊ฑธ๋ฆฌ๋Š”์ง€ ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐ ์‚ฌ์šฉ
  • ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ๋กœ์ง์„ ์ฝ”๋“œ๋กœ ๊ตฌํ˜„ํ•  ๋•Œ, ํšจ์œจ์ ์œผ๋กœ ๊ตฌํ˜„ํ•˜๊ธฐ์œ„ํ•ด ๊ณ ๋ คํ•ด์•ผ ํ•จ
    • ํšจ์œจ์ ์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๊ตฌํ˜„: ์ž…๋ ฅ๊ฐ’์ด ์ปค์ง์— ๋”ฐ๋ผ ์ฆ๊ฐ€ํ•˜๋Š” ์‹œ๊ฐ„์˜ ๋น„์œจ์„ ์ตœ์†Œํ™”ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์„ ๊ตฌ์„ฑ
  • ์ฃผ๋กœ ๋น…-์˜ค ํ‘œ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•ด ๋‚˜ํƒ€๋ƒ„

์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ํ‘œ๊ธฐํ•˜๋Š” ๋ฐฉ๋ฒ•

  • Big-O(Big-Oh, ๋น…-์˜ค) ⇒ ์ƒํ•œ ์ ๊ทผ, ์ตœ์•…์˜ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•
  • Big-Ω(Big-Omega, ๋น…-์˜ค๋ฉ”๊ฐ€) ⇒ ํ•˜ํ•œ ์ ๊ทผ, ์ตœ์„ ์˜ ๊ฒฝ์šฐ์— ๋Œ€ํ•ด ๋‚˜ํƒ€๋‚ด๋Š” ๋ฐฉ๋ฒ•
  • Big-θ(Big-Theta, ๋น…-์„ธํƒ€) ⇒ ๋น… ์˜ค์™€ ๋น… ์˜ค๋ฉ”๊ฐ€์˜ ๊ณตํ†ต๋ถ€๋ถ„, ์ตœ์†Œ์™€ ์ตœ์•…์˜ ์ค‘๊ฐ„์ธ ํ‰๊ท ์ ์ธ ๋ณต์žก๋„

 

Big-O ํ‘œ๊ธฐ๋ฒ•

  • ์ž…๋ ฅ ๋ฒ”์œ„ n์„ ๊ธฐ์ค€์œผ๋กœ ํ•ด์„œ ๋กœ์ง์ด ๋ช‡ ๋ฒˆ ๋ฐ˜๋ณต๋˜๋Š”์ง€ ๋‚˜ํƒ€๋‚ด๋Š” ํ‘œ๊ธฐ๋ฒ•
  •  ‘์ž…๋ ฅ๊ฐ’์˜ ๋ณ€ํ™”์— ๋”ฐ๋ผ ์—ฐ์‚ฐ์„ ์‹คํ–‰ํ•  ๋•Œ, ์—ฐ์‚ฐ ํšŸ์ˆ˜์— ๋น„ํ•ด ์‹œ๊ฐ„์ด ์–ผ๋งˆ๋งŒํผ ๊ฑธ๋ฆฌ๋Š”๊ฐ€?’๋ฅผ ํ‘œ๊ธฐํ•˜๋Š” ๋ฐฉ๋ฒ•

Big-O ํ‘œ๊ธฐ๋ฒ•์˜ ์ข…๋ฅ˜

  1. O(1)
    • ์ผ์ •ํ•œ ๋ณต์žก๋„(constant complexity)๋ผ๊ณ  ํ•˜๋ฉฐ, ์ž…๋ ฅ๊ฐ’์ด ์ฆ๊ฐ€ํ•˜๋”๋ผ๋„ ์‹œ๊ฐ„์ด ๋Š˜์–ด๋‚˜์ง€ ์•Š์Œ
    • ์ž…๋ ฅ๊ฐ’์˜ ํฌ๊ธฐ์™€ ๊ด€๊ณ„์—†์ด, ์ฆ‰์‹œ ์ถœ๋ ฅ๊ฐ’์„ ์–ป์–ด๋‚ผ ์ˆ˜ ์žˆ์Œ
  2. O(n)
    • ์„ ํ˜• ๋ณต์žก๋„(linear complexity)๋ผ๊ณ  ๋ถ€๋ฅด๋ฉฐ, ์ž…๋ ฅ๊ฐ’์ด ์ฆ๊ฐ€ํ•จ์— ๋”ฐ๋ผ ์‹œ๊ฐ„ ๋˜ํ•œ ๊ฐ™์€ ๋น„์œจ๋กœ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธ
    • ์ž…๋ ฅ๊ฐ’์ด ์ปค์ง€๋ฉด ์ปค์งˆ์ˆ˜๋ก ๊ณ„์ˆ˜(n ์•ž์— ์žˆ๋Š” ์ˆ˜)์˜ ์˜๋ฏธ๊ฐ€ ์ ์  ์—†์–ด์ง€๊ธฐ ๋•Œ๋ฌธ์—, ๊ฐ™์€ ๋น„์œจ๋กœ ์ฆ๊ฐ€ํ•˜๊ณ  ์žˆ๋‹ค๋ฉด 2๋ฐฐ๊ฐ€ ์•„๋‹Œ 5๋ฐฐ, 10๋ฐฐ๋กœ ์ฆ๊ฐ€ํ•˜๋”๋ผ๋„ O(n)์œผ๋กœ ํ‘œ๊ธฐ
  3. O(log n)
    • ๋กœ๊ทธ ๋ณต์žก๋„(logarithmic complexity)๋ผ๊ณ  ๋ถ€๋ฅด๋ฉฐ, Big-Oํ‘œ๊ธฐ๋ฒ•์ค‘ O(1) ๋‹ค์Œ์œผ๋กœ ๋น ๋ฅธ ์‹œ๊ฐ„ ๋ณต์žก๋„
  4. O(n2)
    • 2์ฐจ ๋ณต์žก๋„(quadratic complexity)๋ผ๊ณ  ๋ถ€๋ฅด๋ฉฐ, ์ž…๋ ฅ๊ฐ’์ด ์ฆ๊ฐ€ํ•จ์— ๋”ฐ๋ผ ์‹œ๊ฐ„์ด n์˜ ์ œ๊ณฑ์ˆ˜์˜ ๋น„์œจ๋กœ ์ฆ๊ฐ€ํ•˜๋Š” ๊ฒƒ์„ ์˜๋ฏธ
    • n3๊ณผ n5 ๋„ ๋ชจ๋‘ O(n2)๋กœ ํ‘œ๊ธฐ
  5. 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)
๋ฐ˜์‘ํ˜•