中科白癜风医院用疗效说话 http://nb.ifeng.com/a/20180419/6515562_0.shtml实现intsqrt(intx)函数。计算并返回x的平方根，其中x是非负整数。由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。示例：输入：8；输出：2。说明：8的平方根是2.……，由于返回类型是整数，小数部分将被舍去。输入：4；输出：2。数值很大这道题主要考的是二分法求解数值的平方根，然后返回整数，普通方法就是暴力破解，从1开始遍历到这个数值，如果发下n*n=x且(n+1)*(n+1)x，那么这个n就是x的平方根，但是这种方法太暴力，如果n的值很大的时候，可能会出现超时。使用二分法的一个好处是，我们每次都是取中间的数值进行比较，时间复杂度为O(logN)，至于这个值是怎么来的，就是2*n=m，m=log2N。mySqrtPython用二分法实现x的平方根如上代码，每次取start和end的中间值，判断mid*mid=x(mid+1)*(mid+1)，如果这个mid判断正确，那么mid就是x的平方根，如果mix*midx，我们需要做的就是把中间值mid赋值给end，然后再求start和mid之间的值。否则start=mid+1。相比暴力求解的时间复杂度O(n)，你会发现n越来越大的时候，效率就相得益彰了。二分法有个特点就是对数据必须是有序的，其应用场景诸多，比如二分法查找，求除数等等。二分法是面试中算法考察的一个重点，了解二分法可以为你的面试加分不少。人生苦短，我用Python。
转载请注明：http://www.aierlanlan.com/rzgz/7214.html
