爲什麼此函數具有對數時間複雜度（計算數字的第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（含），和這裏的結果：

然後，我相比它（日誌（X）/ step）的情節，並再次這裏的結果：

所以，我有以下問題：

• 爲什麼它是對數？爲什麼這適用於任何數字的第n個根（使用上述方法）不僅平方根？
• 與sqrt增長和log（x）之間的差距是什麼？

我知道有更高效的方法來實現相同的數字平方根結果，但是我需要有人對此進行說明。

Answer 1

當你說循環執行了sqrt(num)次，並且這使得它的複雜度爲√num時，你是正確的。然而，與後面的假設相反，平方根不是對數的：它僅僅是num^(1/2)，這使得它在事物的宏觀方案中是多項式的。

一個明顯的標誌和視覺的幫助是，它不是一個對數圖一條直線：

左邊的線是一個平方根和右邊的線是基礎10對數。

顯然，差距是因爲它不是對數。