實現牛頓法求平方根算法的複雜性

Question

我寫了一個Java程序，用牛頓法計算用戶自定義數的平方根。該算法中的主要操作是這樣說：

answer = guess - ((guess * guess - inputNumber)/(2 * guess)); 
while (Math.abs(answer * answer - inputNumber) > leniency) { 
    guess = answer; 
    answer = guess - ((guess * guess - inputNumber)/(2 * guess)); 
} 

我現在試圖找到該算法的複雜性（燁它的功課），並從here讀了Newton方法的時間複雜度爲O （log（n）* F（x））。

然而，從上面的代碼片段，我已經解釋的時間複雜度爲：

O(1+ ∑(1 to n) (1)) = O(1+n) = O(n) 

不知道什麼我越來越錯在這裏，但我似乎無法理解大的差距Os甚至在閱讀wiki的解釋之後。

此外，我假設「算法的複雜性」與「時間複雜度」是同義的。這樣做是對的嗎？

對於解釋這個悖論，我真的很感謝，因爲我是一個有一些「觸摸和去」編程模塊值得背景的新手。

感謝提前:)

Answer 1

的問題是，你確實知道你計算一無所知n - 你不說，它應該是什麼。當你計算算法的下一次迭代的實際誤差（做它！），你會看到，例如。如果a至少爲1，且錯誤小於1，則基本上每次迭代的有效位數加倍。因此要獲得p小數位數，您必須執行log(p)迭代。