为什么这个函数具有对数时间复杂度(计算数字的第n根)？

Question

上周，我参加了一个关于计算机科学的专门的MOOC课程，还有教授。使用一种低效率的方法来计算一个数字的平方根(后来他还展示了其他方法)。

下面是一个用C++实现的函数：

double sqrt(double num)
{
    double eps = 0.001;
    double step = 0.001;

    double result = 0.0;

    while (num - (result * result) > eps)
    {
        result += step;
    }

    return result;
}

我知道while循环将执行多次( num /step的平方根)。

我决定使用matplotlib来绘制从1到199 (包括在内)的函数增长图，结果如下：

​

​

然后，我将其与(log(x) / step)图进行了比较，结果是：

​

​

因此，我有以下问题：

• 为什么是对数？为什么这适用于任何一个数字的第n根(使用上述方法)，而不仅仅是平方根？
• sqrt增长和log(x)之间的差距是什么？

我知道有更有效的方法来实现一个数字的平方根的相同结果，但我需要有人来解释这个问题。

Answer 1

当您说循环执行sqrt(num)时是正确的，这就使得它的复杂性为√num。然而，与后一种假设相反，平方根不是对数:它只是num^(1/2)，这使得它在事物的整体方案中是多项式的。

一个清晰的标志和视觉帮助是，它不是对数图上的一条直线：

​

​

左边的线是平方根，右边的线是基数10的对数。

差距，很明显，是因为它不是对数。