|
|
马上注册，结交更多好友，享用更多功能^_^
您需要 登录 才可以下载或查看，没有账号？立即注册
x
本帖最后由 zhangjinxuan 于 2023-1-9 14:26 编辑
一：枚举法
思路：设置变量i = 0，如果 i * i > n ,退出循环，否则i++
时间复杂度：O(n ^ 0.5)
代码：
- int solve(int number) {
- int i = 0;
- for (; i * i < number; ++i);
- if (i * i == number) //完全平方数特殊处理
- return i;
- return i - 1;
- }
缺点：只支持整数，时间复杂度高，不太推荐
优点：适合初学者
二：二分法
思路：使用二分答案求出平方根
时间复杂度： O(log2 n)
代码：
- int solve1(int number) {
- int l = 1, r = number;
- while (l + 1 != r) {
- int mid = (l + r) / 2;
- if (mid * mid <= number)
- l = mid;
- else
- r = mid;
- }
- return l;
- }
缺点：只支持整数，比较难懂
优点：时间复杂度低，较推荐
三：小数二分法
思路：在二分答案上做一些改动，使支持小数
时间复杂度：O(log2 n)
- double solve2(double number) {
- double l = 1, r = number;
- while (fabs(l * l - number) > 0.00001) {
- double mid = (l + r) / 2;
- if (mid * mid <= number)
- l = mid;
- else
- r = mid;
- }
- return l;
- }
缺点：虽说是O(log2 n),但某些较大数据可能超时
优点：支持小数，精度较高，较推荐
四：牛顿迭代算法
思路：使用牛顿迭代算法，求出平方根，但因为是大学学的算法，这里不赘述
时间复杂度：O(1)
- double solve3(double number) {
- double x = 1;
- for (int i = 1; i <= 30; ++i) //可以自定义，最好在20以上，数字越高精度越高
- x = (x + number / x) / 2;
- return x;
- }
缺点：太大数据精度可能丢失，理解难
优点：代码简单，精度较高，时间复杂度低，个人推荐
五：牛顿迭代算法+二分（借鉴于CSP-J2022初赛）
思路：牛顿迭代算法加二分，可以减少迭代时循环次数，时间复杂度略显提升
时间复杂度：O(log2 n)
代码：
- int __sqrt1(int number) {
- int l = 1, r = number;
- while (l + 1 != r) {
- int mid = (l + r) / 2;
- if (mid * mid <= number)
- l = mid;
- else
- r = mid;
- }
- return l;
- }
- double solve4(double number) {
- double x = __sqrt1(number);
- for (int i = 1; i <= 10; ++i) //有二分的辅助，循环次数可以适当减少，最好10以上
- x = (x + number / x) / 2;
- return x;
- }
缺点：代码长，有时候聪明反被聪明误，效率并没有提升，而且更不好理解了，不太推荐
优点：精度高，效率还行，
六：cmath
思路：cmath库 sqrt(n) 一行解决（注，需要导入cmath)
代码：
优点：代码短,效率高，懒人福音
缺点：真挑不出毛病... |
评分
-
查看全部评分
|
( 粤ICP备18085999号-1 | 粤公网安备 44051102000585号)
狗仔卡
发表于 2022-9-21 19:15:36
置顶卡
千斤顶
显身卡
楼主
发表于 2022-9-21 19:52:10
