判断自然数是否为平方数

【出自GG面试题】

难度系数：★★★☆☆ 被考察系数：★★★★☆

题目描述：

设计一个算法，判断给定的一个数n是否是某个数的平方，不能使用开方运算。例如16就满足条件，因为它是4的平方；而15则不满足条件，因为不存在一个数使得其平方值为15。

分析与解答：

方法一：直接计算法

由于不能使用开方运算，因此最直接的方法就是计算平方。主要思路：对1到n的每个数i，计算它的平方m，如果m＜n，则继续遍历下一个值（i+1），如果m==n，那么说明n是m的平方，如果m＞n，那么说明n不能表示成某个数的平方。实现代码如下：

程序的运行结果如下：

15不是某个自然数的平方

16是某个自然数的平方

算法性能分析：

由于这种方法只需要从1遍历到n^0.5就可以得出结果，因此算法的时间复杂度为O（n^0.5）。(www.xing528.com)

方法二：二分查找法

与方法一类似，这种方法的主要思路还是查找从1～n的数字中，是否存在一个数m，使得m的平方为n。只不过在查找的过程中使用的是二分查找的方法。具体思路是：首先判断mid=（1+n）/2的平方power与m的大小，如果power＞m，那么说明在[1，mid-1]区间继续查找，否则在[mid+1，n]区间继续查找。

实现代码如下：

算法性能分析：

由于这种方法使用了二分查找的方法，因此，时间复杂度为O（log₂ⁿ），其中，n为数的大小。

方法三：减法运算法

通过对平方数进行分析发现有如下规律：

（n+1）^2=n^2+2n+1=（n-1）^2+（2*（n-1）+1）+2*n+1=…=1+（2*1+1）+（2*2+1）+…+（2*n+1）。通过上述公式可以发现，这些项构成了一个公差为2的等差数列的和。由此可以得到如下的解决方法：对n依次减1，3，5，7，…，如果相减后的值大于0，则继续减下一项；如果相减后的值等于0，则说明n是某个数的平方；如果相减的值小于0，则说明n不是某个数的平方。根据这个思路，代码实现如下：

算法性能分析：

这种方法的时间复杂度仍然为O（n^0.5）。由于方法一使用的是乘法操作，这种方法采用的是减法操作，因此这种方法的执行效率比方法一更高。