๋น…์˜คํ‘œ๊ธฐ๋ฒ• 1
๋น…์˜ค(Big-O) ํ‘œ๊ธฐ๋ฒ•

๋น…์˜ค(Big-O)๋ž€, ์ฝ”๋“œ์—์„œ ๋ฐ์ดํ„ฐ๊ฐ€ ๋Š˜์–ด๋‚  ๋•Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์„ฑ๋Šฅ์„ ํ‘œ๊ธฐํ•˜๋Š” ๋ฐฉ๋ฒ•์ด๋‹ค. ๋‹จ์ˆœํžˆ ์ฝ”๋“œ๊ฐ€ '์ข‹๋‹ค', '๋‚˜์˜๋‹ค'๋กœ ํ‘œํ˜„ํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹Œ ์ˆซ์ž๋กœ ์ฝ”๋“œ์˜ ์„ฑ๋Šฅ์„ ํ‘œ๊ธฐํ•˜๊ธฐ ์œ„ํ•ด ๋น…์˜ค ํ‘œ๊ธฐ๋ฒ•์„ ์‚ฌ์šฉํ•œ๋‹ค. ์ž…๋ ฅ์˜ ํฌ๊ธฐ์™€ ์‹คํ–‰ ์‹œ๊ฐ„๊ณผ์˜ ๊ด€๊ณ„๋ผ๊ณ  ํ•  ์ˆ˜ ์žˆ๋‹ค. ๋ฐ์ดํ„ฐ ์›์†Œ๊ฐ€ N๊ฐœ์ผ ๋•Œ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ๋ช‡ ๋‹จ๊ณ„๊ฐ€ ํ•„์š”ํ• ๊นŒ? O(1)๊ณผ O(N) ์œ„์˜ ๊ทธ๋ž˜ํ”„์—์„œ x์ถ•์„ ๋ฐ์ดํ„ฐ ์ˆ˜๋กœ ๋ดค์„ ๊ฒฝ์šฐ, O(N)์˜ ๊ทธ๋ž˜ํ”„๋Š” ๋ฐ์ดํ„ฐ์˜ ์ˆ˜๊ฐ€ ๋Š˜์–ด๋‚ ์ˆ˜๋ก ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋‹จ๊ณ„๋„ ๋Š˜์–ด๋‚œ๋‹ค. ์ฆ‰, ๋ฐ์ดํ„ฐ๊ฐ€ 1000๊ฐœ๊ฐ€ ๋˜๋ฉด ์•Œ๊ณ ๋ฆฌ์ฆ˜๋„ 1000๋‹จ๊ณ„๊ฐ€ ๊ฑธ๋ฆฐ๋‹ค. O(1)์˜ ๊ทธ๋ž˜ํ”„๋ฅผ ๋ณด๋ฉด ๋ฐ์ดํ„ฐ๊ฐ€ 1๊ฐœ์ด๊ฑฐ๋‚˜ 1000๊ฐœ์ด๊ฑฐ๋‚˜ ์•Œ๊ณ ๋ฆฌ์ฆ˜์€ ํ•ญ์ƒ 100๋‹จ๊ณ„๊ฐ€ ๊ฑธ๋ฆฐ๋‹ค. ๋ฐ์ดํ„ฐ๊ฐ€ 100๊ฐœ ๋ฏธ๋งŒ์ผ ๊ฒฝ์šฐ์—” O(N)์ด ๋น ๋ฅผ ์ˆ˜ ์žˆ๊ฒ ์ง€๋งŒ, ๊ทธ ์ด์ƒ์œผ๋กœ ๋„˜์–ด๊ฐ€๋ฉด O(N)์˜..
๊ฐœ๋ฐœ ๊ณต๋ถ€/์•Œ๊ณ ๋ฆฌ์ฆ˜ 2024.01.11
1
๋”๋ณด๊ธฐ

ํ‹ฐ์Šคํ† ๋ฆฌํˆด๋ฐ”