202. 快乐数的复杂度分析

Question

https://github.com/liuyubobobo/Play-Leetcode/blob/master/0202-Happy-Number/cpp-0202/main.cpp
老师，这个的复杂度是怎么分析出两个O(logN)的啊？？

Answer 1

liuyubobobo 2020-11-22 03:08:25

这个问题比较数学了，面试肯定不会考这种复杂度分析。

简单解释一下：

从一个数出发，根据题目的规则，有三种可能：

1）最终成为 1，那么它就是快乐数；

2）最终陷入一个循环，而这个循环里没有1，那么他就是不快乐数；

3）没有陷入循环，而且越来越大。

第 3）种可能因为计算向着无穷的方向发展，会使得我们的算法复杂度是无穷的，所以我们分析一下是否可能出现 3）？

答案是不可能。

一个一位数字，平方和的结果最大为 81(数字 9)

一个两位数字，平方和的结果最大为 162(数字 99)

一个三位数字，平方和的结果最大为 243(数字 999)

一个四位数字，平方和的结果最大为 324(数字 9999)

很容易验证，从四位数往上，平方和结果的数字位数肯定是更小的。

所以，任何一个数字，按照题目规则，肯定要走到一个三位数或者更小的数字。而进入三位数，就不可能再升到四位数字或者更大的数字了。

所以，我们搜索的数字，最多也就是所有的三位数字的可能，也就是 999，这是一个常数。

对于一个 n，处理它需要 logn 的时间，我们最多处理 999 这个级别的数字（常数级别），所以整体是 logn 的复杂度。

继续加油！：）

• 提问者 邹正霖 #1

  非常感谢！