[์•Œ๊ณ ๋ฆฌ์ฆ˜] ๊ณผ์ œ 1. ์‹œ๊ฐ„ ๋ณต์žก๋„ ๊ณ„์‚ฐ :: ๊ฐ ์‹œ๊ฐ„ ๋ณต์žก๋„์— ํ•ด๋‹นํ•˜๋Š” ์†Œ์š”์‹œ๊ฐ„์„ ๊ตฌํ•ด๋ณด์ž
์ปดํ“จํ„ฐ๊ณผํ•™ (CS)/Algorithm 2020. 3. 25. 19:52

์ฒซ๋ฒˆ์งธ ๊ณผ์ œ์ด๋‹ค. ์‹œ๊ฐ„ ๋ณต์žก๋„๊ฐ€ f(n)์ธ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์†Œ์š”์‹œ๊ฐ„์ด 1 nanosecond == 10^(-9) second ์ด๋ผ๊ณ  ํ•  ๋•Œ, ์™ผ์ชฝ์— ํ‘œ์‹œ๋œ ์‹œ๊ฐ„ ๋ณต์žก๋„๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด ์œ„์ชฝ์˜ ์‹œ๊ฐ„ ๋‚ด์— ์•Œ๊ณ ๋ฆฌ์ฆ˜์ด ์™„๋ฃŒ๋˜๋ ค๋ฉด ์ตœ๋Œ€๋กœ ์–ด๋–ค N๊นŒ์ง€ ๊ณ„์‚ฐํ•  ์ˆ˜ ์žˆ์„์ง€ ์•Œ์•„๋ณด์ž. ๋Œ€ํ‘œ๋กœ ํ•˜๋‚˜๋ฅผ ๊ณ„์‚ฐํ•ด๋ณด๋ฉด 1sec๋Š” 10^(9) nanosec ์ด๋ฏ€๋กœ n^2์˜ ์‹œ๊ฐ„๋ณต์žก๋„๋ฅผ ๊ฐ–๋Š” ์•Œ๊ณ ๋ฆฌ์ฆ˜์—์„œ n^2 = 10^(9) ๋กœ ๋‘๊ณ  ํ’€๋ฉด 1sec ๋งŒ์— ๊ณ„์‚ฐ๋  ์ˆ˜ ์žˆ๋Š” n ๊ฐ’์ด ๋‚˜์˜จ๋‹ค. n ๊ฐ’์€ ๋ชจ๋‘ ์ •์ˆ˜๋กœ ๊ฐ€์ •ํ•˜์˜€๋‹ค.