์ด ๊ณ์ฐ๊ธฐ๋ ๋ฌด์์ ํ๋์
์ด ๋๊ตฌ๋ ์ฒ์ n๊ฐ์ ์์ ์ธ์ ๊ณฑ์์ ํฉ, ์ฆ \(1^3 + 2^3 + 3^3 + \ldots + n^3\)์ ๊ณ์ฐํฉ๋๋ค. ๋ชจ๋ ํญ์ ํ๋์ฉ ๋ํ๋ ๋์ , ์ ๋ช ํ ๋ซํ ๊ณต์(closed-form)์ ์ฌ์ฉํด n์ด ์๋ฌด๋ฆฌ ์ปค๋ ์ ํํ ๋ต์ ์ฆ์ ๊ตฌํด์ค๋๋ค.
์ฌ์ฉ ๋ฐฉ๋ฒ
ํญ์ ๊ฐ์ n์ ์์ ์ ์๋ฅผ ์ ๋ ฅํ๋ฉด ๊ฒฐ๊ณผ๊ฐ ๋ฐ๋ก ํ์๋ฉ๋๋ค. ๋ํ ๋ต์ด ์ด๋ป๊ฒ ๋ง๋ค์ด์ง๋์ง ์ ์ ์๋๋ก ๊ทธ ๋ฐํ์ด ๋๋ ์ผ๊ฐ์ \(n(n+1)/2\)๋ ํจ๊ป ๋ณด์ฌ์ค๋๋ค.
๊ณต์ ์ค๋ช
ํต์ฌ์ด ๋๋ ๊ฒฐ๊ณผ๋ ๋์ฝ๋ง์ฝ์ค ํญ๋ฑ์(Nicomachus identity)์ ๋๋ค.
$$\sum_{k=1}^{n} k^{3} = \left( \frac{n\left(n+1\right)}{2} \right)^{2}$$
๋๋๊ฒ๋ ์ฒ์ n๊ฐ ์ธ์ ๊ณฑ์ ํฉ์ ์ฒ์ n๊ฐ ์ ์์ ํฉ์ ์ ๊ณฑํ ๊ฐ๊ณผ ์ ํํ ๊ฐ์ต๋๋ค. ์์ชฝ์ \(n(n+1)/2\)๋ n๋ฒ์งธ ์ผ๊ฐ์ \(T(n)\)์ด๋ฏ๋ก, ์ธ์ ๊ณฑ์ ํฉ์ ๊ณง \(T(n)\)์ ์ ๊ณฑํ ๊ฐ์ ๋๋ค. ๋๋ถ์ ๋ฐ๋ณต ๊ณ์ฐ ์์ด \(O(1)\)๋ก ์ฒ๋ฆฌํ ์ ์์ผ๋ฉฐ, ์ ์ ์ ๋ ฅ์ ๋ํด ํญ์ ์ ํํ ๊ฐ์ ์ค๋๋ค.
์์ ํ์ด
n = 4์ธ ๊ฒฝ์ฐ: ์ผ๊ฐ์๋ \(4\times 5/2 = 10\)์ ๋๋ค. ์ด๋ฅผ ์ ๊ณฑํ๋ฉด \(10^2 = 100\)์ด ๋ฉ๋๋ค. ์ง์ ๋ํด์ ํ์ธํด ๋ณด๋ฉด \(1 + 8 + 27 + 64 = 100\)์ผ๋ก ์ผ์นํ๋ฏ๋ก, ํญ๋ฑ์์ด ์ฑ๋ฆฝํจ์ ์ ์ ์์ต๋๋ค.
์์ฃผ ๋ฌป๋ ์ง๋ฌธ
์ ์์ ๋ํด์๋ง ์๋ํ๋์? ๋ค โ ์ด ํญ๋ฑ์์ k = 1๋ถํฐ n๊น์ง ์ ์ ํญ์ ๋ํ ํฉ์ ์ ์ฉ๋๋ฏ๋ก, n์ ์์ ์ ์์ฌ์ผ ํฉ๋๋ค.
์ ๋ต์ ํญ์ ์์ ์ ๊ณฑ์์ธ๊ฐ์? ํฉ์ด \(T(n)^2\)๊ณผ ๊ฐ๊ธฐ ๋๋ฌธ์ ๋๋ค. ์ฌ๊ธฐ์ \(T(n)\)์ n๋ฒ์งธ ์ผ๊ฐ์์ด๋ฉฐ, ์ ์๋ฅผ ์ ๊ณฑํ๋ฉด ํญ์ ์์ ์ ๊ณฑ์๊ฐ ๋ฉ๋๋ค.
n์ด ์์ฃผ ์ปค๋ ๋๋์? ๋ค. ๋ซํ ๊ณต์์ด๋ฏ๋ก n์ด ์ปค๋ ์ฆ์ ๊ณ์ฐ๋ฉ๋๋ค. ๋ค๋ง ๊ฐ์ด ์ง๋์น๊ฒ ํฌ๋ฉด ์ผ๋ฐ์ ์ธ ๋ถ๋์์์ ์ ๋ฐ๋๋ฅผ ๋์ด์ค ์ ์์ต๋๋ค.