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));
}

我现在正在寻找算法的复杂性（是的，这是家庭作业），并且从这里读到牛顿方法的时间复杂度是 O(log(n) * F(x))。

但是，从上面的代码片段中，我将时间复杂度解释为：

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

不知道我在这里做错了什么，但即使在阅读了维基的解释之后，我似乎也无法理解大操作系统的差异。

另外，我假设“算法的复杂性”是“时间复杂性”的同义词。这样做是否正确？

非常感谢帮助解释这个悖论，因为我是一个新手学生，有一些“触摸即走”编程模块的背景知识。

提前致谢 ：）

Answer 1

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