青龙建站教程自学网_宁波本地模板网站建设平台_广告联盟官网_网站建设制作流程

问题描述

• 输入一个非负整数 x，返回它的平方根的整数部分。
• 不使用内置的 sqrt 函数。
• 要求时间复杂度尽可能小。

示例

1. 输入：

   x = 4
   

   输出：

   2
   

2. 输入：

   x = 8
   

   输出：

   2
   

   解释： $\sqrt{8}\approx 2.82842$，只取整数部分。

---

解题思路

方法 1：二分查找

平方根问题可以转化为一个单调性问题：

• 对于任意非负整数 x，其平方根满足：${\text{mid}}^2\le x<(\text{mid}+1{)}^2$。
• 因此，可以使用二分查找来快速缩小范围。

方法 2：牛顿迭代法

牛顿迭代法是一种快速求解平方根的数值方法，通过不断逼近平方根来求解。

• 初始猜测为 $g=x$。
• 更新公式为 $g=\frac{g+\frac{x}{g}}{2}$，直到满足 $g^2\approx x$。

---

代码实现

方法 1：二分查找

#include <stdio.h>int mySqrt(int x) {if (x == 0 || x == 1) {return x;}int left = 0, right = x, ans = 0;while (left <= right) {int mid = left + (right - left) / 2;if ((long long)mid * mid == x) {return mid; // 找到精确平方根} else if ((long long)mid * mid < x) {ans = mid; // mid 是当前的最大可能解left = mid + 1;} else {right = mid - 1;}}return ans;
}int main() {int x = 8;printf("sqrt(%d) = %d\n", x, mySqrt(x));return 0;
}

---

方法 2：牛顿迭代法

#include <stdio.h>int mySqrt(int x) {if (x == 0 || x == 1) {return x;}double guess = x; // 初始猜测while (1) {double nextGuess = (guess + x / guess) / 2;if ((int)guess == (int)nextGuess) { // 当整数部分不再变化时，退出break;}guess = nextGuess;}return (int)guess;
}int main() {int x = 8;printf("sqrt(%d) = %d\n", x, mySqrt(x));return 0;
}

---

复杂度分析

时间复杂度

1. 二分查找：
   • 每次二分缩小范围，时间复杂度为 $O(\log x)$。
2. 牛顿迭代法：
   • 收敛速度非常快，时间复杂度为 $O(\log x)$。

空间复杂度

• 两种方法均为 $O(1)$。

---

测试示例

输入输出

1. 输入 x = 4：

   sqrt(4) = 2
   

2. 输入 x = 8：

   sqrt(8) = 2
   

3. 输入 x = 0：

   sqrt(0) = 0
   

4. 输入 x = 2147395599（大数测试）：

   sqrt(2147395599) = 46339