Python面试宝典第37题：有效的完全平方数

情感恶魔

题目        完全平方数是一个可以写成某个整数的平方的整数，换句话说，它可以写成某个整数和自身的乘积。现给你一个正整数num，如果num是一个完全平方数，则返回true，否则返回false。        注意：不能使用任何内置的库函数（比如：sqrt）。        示例1：输入：num=16输出：true解释：返回true，因为4*4=16，且4是一个整数。        示例2：输入：num=14输出：false解释：返回false，因为3.742*3.742=14，但3.742不是一个整数。暴力法        暴力法求解一个数是否为完全平方数的基本思想是：通过遍历所有可能的平方根，来确定是否存在一个整数的平方恰好等于给定的数。使用暴力法求解本题的主要步骤如下。        1、初始化i为1。        2、当i*inum，则更新右端点为mid-1。        3、如果搜索结束后仍未找到符合条件的mid，则返回False，表示num不是一个完全平方数。        根据上面的算法步骤，我们可以得出下面的示例代码。defis_perfect_square_by_binary_search(num):ifnumnum，故其时间复杂度为O(n的平方根)。暴力法的优点是实现简单，易于理解，但效率较低，特别是对于较大的num。        使用二分搜索法时，搜索区间每次减半，因此时间复杂度为O(logn)。相对于暴力法，二分搜索法的效率更高，且实现并不复杂。        牛顿迭代法的收敛速度非常快，通常只需要几次迭代就可以达到很高的精度，其时间复杂度为O(log(logn))。牛顿迭代法的效率非常高，尤其在num较大时，表现更佳。💡需要《Python面试宝典》完整源码的大佬们，可订阅专栏后，搜索微信公众号“希望睿智”私信获取。