分類
發燒車訊

實現 sqrt(x):二分查找法和牛頓法

最近忙裡偷閑,每天刷一道 LeetCode 的簡單題保持手感,發現簡單題雖然很容易 AC,但若去了解其所有的解法,也可學習到不少新的知識點,擴展知識的廣度。

創作本文的思路來源於:

簡述題目大意(不想跳轉鏈接,可以看這裏):給定一個非負整數 x,要求計算並返回 x 的平方根(取整)。例如,輸入 4,則輸出 2;輸入 8,則輸出 2(8 的平方根是 2.82842……,由於返回類型是整數,因此小數部分被捨去)。即給定一個 \(x\),我們要計算出 \(\lfloor \sqrt{x} \rfloor\)

最簡單最直覺的方法自然是從 0 開始遍歷,直到找到第一個其平方值大於 \(x\) 的數 \(n\),則 \(n-1\) 即是答案。對於任意的 \(x\),其取整后平方根一定在 \([0, x]\) 區間上,代碼如下:

int sqrt(int x)
{
    if (x == 0)
        return x;
    int ans = 1;
    while (ans <= x / ans)
        ans++;
    return ans - 1;
}

這裏需要注意的有兩點:

  1. 第 6 行代碼中,while 的判斷條件可以避免溢出。很大概率上,你可能會寫成 while (ans * ans <= x),這更自然、更直觀,但當 ans 的值很大時,ans * ans 的結果可能會超過 int 類型的最大表示範圍。舉個例子,比如我們要計算 \(x\) 的取整平方根(其值為 \(n\),即 \(\lfloor \sqrt{x} \rfloor = n\)),算法會將 ans 遍歷到第一個平方超過 \(x\) 的值,即 \(n+1\) 后停止。如果 \(x\) 的值就是 int 類型能夠表示的最大值,那麼當 ans 遍歷到 \(n+1\) 時,計算 ans * ans 的結果就超出了 int 類型的表示範圍。
  2. 由於在 while 的循環判斷中,我們用除法代替了乘法,因此 ans 便不能再從 0 開始遍歷(否則會導致除零錯誤)。為此,我們可以在算法開始單獨處理 \(x = 0\) 的情況,然後讓 ans 從 1 開始遍歷。

作為一道簡單題,這種暴力樸素的算法自然是可以 AC 的。但其效率極低(需要遍歷 \(O(\sqrt{n})\) 次),在 LeetCode 上的時間效率只能快過約 5% 的用戶,使用 C++ 語言的運行時間平均要 90ms 以上。因此,本文提供了兩種更加高效的算法:二分查找法和牛頓法。

1. 二分查找法

如果你在暴力求解的基礎上繼續思考,很大概率會想到用二分搜索求解。

沒錯,思考暴力求解的策略,我們在區間 \([0, x]\) 上搜索解,而搜索區間 \([0, x]\) 天然是有序的,自然可以用二分搜索代替線性搜索,以大大提高搜索效率。

更進一步的,我們還可以縮小我們的搜索區間。直覺告訴我們,對於一個非負整數 \(x\),其 \(\sqrt{x}\) 應該不會大於 \(x / 2\)(例如,\(\sqrt{25} = 5\),小於 \(25 / 2 = 12.5\))。我們可以證明:

\[ \begin{aligned} &\text{設 } y = \frac{x}{2} – \sqrt{x},\text{ 則 } y^\prime = \frac{1}{2} – \frac{1}{2\sqrt{x}}, \\[2ex] &\text{令 } y^\prime = 0, \text{ 可得駐點 } x = 1, \\[2ex] &\text{當 } x > 1 \text{ 時}, y^\prime > 0, \text{ 即當 } x > 1 \text{ 時 }, y = \frac{x}{2} – \sqrt{x} \text{ 的值單調遞增}, \\[2ex] &\text{可推出, 當 } x > 1 \text{ 時}, \lfloor \frac{x}{2} \rfloor – \lfloor \sqrt{x} \rfloor \text{ 的值單調遞增}, \\[2ex] &\text{又因為當 } x = 2 \text{ 時}, \lfloor \frac{x}{2} \rfloor – \lfloor \sqrt{x} \rfloor = 0, \\[2ex] &\text{所以當 } x \geq 2 \text{ 時}, \lfloor \frac{x}{2} \rfloor – \lfloor \sqrt{x} \rfloor \geq 0, \text{ 即 } x \geq 2 \text{ 時},\lfloor \frac{x}{2} \rfloor \geq \lfloor \sqrt{x} \rfloor &\text{(證畢)} \end{aligned} \]

通過證明我們可以得知,當所求的 \(x\) 大於等於 \(2\) 時,sqrt(x) 的搜索空間為 \([1, x / 2]\),對於 \(x < 2\) 的情況,我們只要特殊處理即可(這裏我們也可以得到結論:當 \(x \geq 1\) 時,\(\lfloor \frac{x}{2} \rfloor + 1 \geq \lfloor \sqrt{x} \rfloor\),然後單獨處理 \(x < 1\) 的情況)。代碼:

int sqrt(int x)
{
    if (x < 2)  // 處理特殊情況
        return x;
    
    int left = 1, right = x / 2;
    while (left <= right) {
        # 避免溢出,相當於 mid = (left + right) / 2
        int mid = left + ((right - left) >> 1);
        if (mid == x / mid)
            return mid;
        else if (mid > x / mid)
            right = mid - 1;
        else
            left = mid + 1;
    }
    return right;
}

在這裏解釋一下最後的返回值為什麼是 right。對於二分查找,其搜索空間會不斷收縮到 left == right(關於二分查找,這裏不多贅述,自行手動模擬即可),此時 midleftright 三者的值相等(mid = (left + right) / 2)。根據二分查找的搜索範圍的收縮條件可知,left(或 mid)左側的值都小於等於 \(\lfloor \sqrt{x} \rfloor\)right(或 mid)右側的值都大於 \(\lfloor \sqrt{x} \rfloor\),此時(while 的最後一次循環),判斷 mid 的平方與 x 的大小,有三種情況:

  1. mid == x / mid。則在循環內直接返回 mid 的值。
  2. mid > x / mid。這種情況下,因為 mid 左側的值都小於等於 \(\lfloor \sqrt{x} \rfloor\),而 mid 的值大於 \(x\),則 mid-1 即是答案。而按照分支條件,執行 right = mid - 1,可知 right 的值正是應返回的值。此時,循環結束,應返回 right
  3. mid <= x / mid。這種情況下,midleftright 正是計算答案(右邊的值都大於 \(\lfloor \sqrt{x} \rfloor\))。按照分支條件,執行 left = mid + 1,循環結束。此時,midright 的值為計算結果。

綜合上面三點可知,如果 while 循環結束,則 right 保存的值一定是計算結果。

和之前的暴力法相比,使用二分查找的思想求解 sqrt(x),只需要循環遍歷 \(O(\lg{\frac{x}{2}})\) 次;空間複雜度為 \(O(1)\)

2. 牛頓—拉弗森迭代法

牛頓—拉弗森迭代法(簡稱牛頓法)使用以直代曲的思想,是一種求解函數的方法,不僅僅適用於求解開方計算。當然使用牛頓法求解函數也存在很多坑,但對於求解開方而言,牛頓法是安全的。關於這一方法,你需要掌握一定的高等數學知識,想了解詳細的內容,可以參考鏈接:

簡單的理解,可以參考圖片:

圖片來源:

給定任意一個非負整數 \(n\),我們想要找到一個 \(x = \lfloor \sqrt{n} \rfloor\),這相當於我們要計算函數 \(f(x) = x^2 – n\) 的根。我們首先需要先給出一個猜測值 \(x_0\),不妨令 \(x_0 = \frac{x}{2} + 1\)(證明見第一小節),然後在 \(f(x_0)\) 處作函數的切線,切線與 \(x\) 軸的交點,即為一次迭代后的值 \(x_1\)。若 \(x_1\) 不是要得到的結果,則繼續迭代,在 \(f(x_1)\) 處作函數的切線,切線與 \(x\) 軸的交點,即為第二次迭代后的值 \(x_2\)。以此類推,直到得到 \(x_n = \lfloor \sqrt{n} \rfloor\)

現在我們來推導迭代式。對於 \(x_i\),其函數值為 \(f(x_i)\),則對於點 \((x_i, f(x_i))\),可得其切線方程:

\[ \begin{align} &y – f(x_i) = f(x_i)^\prime(x – x_i) \\[2ex] \implies &y – (x_i^2 – n) = 2x_i(x – x_i) \\[2ex] \implies &y + x_i^2 + n = 2x_ix \end{align} \]

又因為 \(x_{i+1}\) 為切線與 \(x\) 軸的交點,所以令 \(y=0\),可得:

\[ x_{i+1} = (x_i + n / x_i) / 2 \]

現在,我們就可以根據迭代式編寫代碼了:

int sqrt(int x)
{
    // 避免除零錯誤,單獨處理 x = 0 的情況
    if (x == 0)
        return x;
    int t = x / 2 + 1;
    while (t > x / t)
        t = (t + x / t) / 2;
    return t;
}

為了確保算法是正確的,我們還需要一些額外的證明。首先,證明迭代式是單調遞減的:

\[ x_{i+1} – x_i = \left\lfloor \frac{1}{2} (x_i + \frac{n}{x_i}) \right\rfloor – x_i = \left\lfloor \frac{1}{2} (\frac{n}{x_i} – x_i) \right\rfloor \]

可知,在區間 \([\sqrt{x}, +\infty)\) 上,\(x_{i+1} – x_i < 0\)

然後,我們還要證明迭代式是可以收斂到 \(\lfloor \sqrt{n} \rfloor\) 的:

\[ x_{i+1} = \left\lfloor \frac{1}{2} \left( x_i + \left\lfloor \frac{n}{x_i} \right\rfloor \right) \right\rfloor = \left \lfloor \frac{1}{2} (x_i + \frac{n}{x_i}) \right \rfloor \geq \left \lfloor \frac{1}{2} \times 2 \times \sqrt{x_i \cdot \frac{n}{x_i}} \right \rfloor = \lfloor \sqrt{n} \rfloor \]

因此,當 while 循環結束時,我們可以得到正確的答案。

關於牛頓法求 sqrt(x) 的時間複雜度,筆者目前也沒有搞清楚,有了解的童鞋歡迎交流~。不過通過查詢資料,以及實際測試,可知牛頓法的時間效率優於二分搜索法。

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

【其他文章推薦】

網頁設計公司推薦更多不同的設計風格,搶佔消費者視覺第一線

※廣告預算用在刀口上,網站設計公司幫您達到更多曝光效益

※自行創業 缺乏曝光? 下一步"網站設計"幫您第一時間規劃公司的門面形象

南投搬家前需注意的眉眉角角,別等搬了再說!