估計的執行計算所需的操作數量

Question

我有一個等式：

∑ _1到n J（1）2 = N＆middot; （n + 1）＆middot; （2n + 1）/ 6

問題希望我估計在等式的左側和右側執行計算所需的操作次數。

對於左側，我發現：

爲O（n＆middot;登錄^ 2（n））的

但右邊，我不知道如何下手......

Answer 1

由於n給定，做計算(n+1)*(2n+1)/6在恆定時間，即完成ö（1）

Answer 2

左側爲O（n）如果假設計算J（1）圖2是一個恆定的時間OPERAT離子。如果不是（如果n可能真的很大），那麼如果使用巧妙的方法計算j^2，那麼它就是O（n log n log log n），或者如果你使用那個j^2 =（ j - 1）^ 2 + 2j + 1.

如果我正確計數，右邊是六個操作，這使得它成爲O（1）。或者如果你輸入了非常大的n，例如一百萬位數字，那麼O（log n log log n）。