最近忙里偷閑，每天刷一道 LeetCode 的簡單題保持手感，發現簡單題雖然很容易 AC，但若去了解其所有的解法，也可學習到不少新的知識點，擴展知識的廣度，
創作本文的思路來源于：LeetCode Problem 69. x 的平方根
簡述題目大意（不想跳轉鏈接，可以看這里）：給定一個非負整數 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;
}
這里需要注意的有兩點：
- 第 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型別的表示范圍， - 由于在
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（關于二分查找，這里不多贅述，自行手動模擬即可），此時 mid、left和 right 三者的值相等（mid = (left + right) / 2），根據二分查找的搜索范圍的收縮條件可知，left（或 mid）左側的值都小于等于 \(\lfloor \sqrt{x} \rfloor\)，right（或 mid）右側的值都大于 \(\lfloor \sqrt{x} \rfloor\)，此時（while 的最后一次回圈），判斷 mid 的平方與 x 的大小，有三種情況：
mid == x / mid，則在回圈內直接回傳mid的值，mid > x / mid，這種情況下，因為mid左側的值都小于等于 \(\lfloor \sqrt{x} \rfloor\)，而mid的值大于 \(x\)，則mid-1即是答案，而按照分支條件，執行right = mid - 1，可知right的值正是應回傳的值，此時，回圈結束，應回傳right，mid <= x / mid，這種情況下，mid、left和right正是計算答案（右邊的值都大于 \(\lfloor \sqrt{x} \rfloor\)），按照分支條件，執行left = mid + 1，回圈結束，此時，mid和right的值為計算結果，
綜合上面三點可知，如果 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) 的時間復雜度，筆者目前也沒有搞清楚，有了解的童鞋歡迎交流~，不過通過查詢資料，以及實際測驗，可知牛頓法的時間效率優于二分搜索法，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/125572.html
標籤：其他
上一篇：歸并排序
下一篇：淺談資料結構概念