๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

์žฌ๊ท€ํ•จ์ˆ˜1

ํ”ผ๋ณด๋‚˜์น˜ ํŒŒ์ด์ฌ์œผ๋กœ ๊ตฌํ•˜๋Š” 3๊ฐ€์ง€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ”ผ๋ณด๋‚˜์น˜ ํŒŒ์ด์ฌ 3๊ฐ€์ง€ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์€ ์•„๋ž˜์˜ ์ˆ˜์‹์€ ๋งŒ์กฑํ•˜๋Š” ์ˆ˜์—ด์ž…๋‹ˆ๋‹ค. ๋ฐ”๋กœ ์ด์ „ ์ˆซ์ž์™€ ๊ทธ ์ „ ์ˆซ์ž์˜ ํ•ฉ์„ ์—ฐ์†ํ•ด์„œ ๊ตฌํ•˜๋Š” ์ˆ˜์—ด์ด๊ณ  ์•„๋ž˜์™€ ๊ฐ™์ด ์ง„ํ–‰๋ฉ๋‹ˆ๋‹ค. ์ด๋ฒˆ ๊ธ€์—์„œ๋Š” ์‹œ๊ฐ„ ๋ณต์žก๋„์— ๋”ฐ๋ฅธ ํ”ผ๋ณด๋‚˜์น˜ ์ˆ˜์—ด์„ ๊ตฌํ•˜๋Š” ๋Œ€ํ‘œ์ ์ธ 3๊ฐ€์ง€ ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ๋Œ€ํ•ด์„œ ์•Œ์•„๋ณด๋„๋ก ํ•˜๊ฒ ์Šต๋‹ˆ๋‹ค. ์žฌ๊ท€ํ•จ์ˆ˜ ์ด์šฉ - ์‹œ๊ฐ„๋ณต์žก๋„ O(n^2) ๋™์  ๊ณ„ํš๋ฒ• ์ด์šฉ - ์‹œ๊ฐ„๋ณต์žก๋„ O(n) ํ–‰๋ ฌ ๋ฉฑ๋ฒ• ์ด์šฉ - ์‹œ๊ฐ„๋ณต์žก๋„ O(log n) ์žฌ๊ท€ํ•จ์ˆ˜ ์ด์šฉ ์ฒซ๋ฒˆ ์งธ ๋ฐฉ๋ฒ•์€ ์žฌ๊ท€ํ•จ์ˆ˜๋ฅผ ์ด์šฉํ•˜๋Š” ๋ฐฉ๋ฒ•์ž…๋‹ˆ๋‹ค. def fibo(n): if n in (1,2): return 1 return fibo(n-1) + fibo(n-2) print(fibo(8)) ๊ฐ€์žฅ ๊ฐ„๋‹จํ•œ ๋ฐฉ๋ฒ•์ด์ง€๋งŒ... ์žฌ๊ท€๋กœ ๋‘๊ฐœ์˜ ๋ถ„๊ธฐ๊ฐ€ ๊ณ„์†ํ•ด์„œ ์ƒ๊ธฐ๊ธฐ ๋•Œ๋ฌธ์— ์‹œ๊ฐ„๋ณต์žก๋„๊ฐ€ O(.. 2021. 10. 8.