java - 实现牛顿法求平方根的算法的复杂性

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牛顿法的时间复杂度为O(log(n) * F(x))。

但是，根据上面的代码片段，我将时间复杂度解释为:

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

不确定我在这里犯了什么错误，但即使在阅读了 wiki 的解释之后，我似乎也无法理解 big Os 中的差异。

此外，我假设“算法的复杂性”是“时间复杂性”的同义词。这样做对吗？

非常感谢您帮助解释这个悖论，因为我是一名新手学生，拥有一些值得背景知识的“即插即用”编程模块。

提前致谢:)

Answer 1

问题是您在计算中实际上对 n 一无所知——您没有说明它应该是什么。当你计算算法下一次迭代的实际误差时(做吧!)，你会看到，例如。如果 a 至少为 1 且错误小于 1，则基本上每次迭代都将有效位置的数量加倍。因此，要获得 p 小数位，您必须执行 log(p) 迭代。