Leetcode 如何理解快乐数问题解决的时间复杂度

Question

我在理解 Leet 代码的快乐数字问题的一种解决方案的时间复杂度分析方面遇到了一些困难，对于我对复杂性分析的疑问，我将它们用粗体标记，非常感谢你的建议

这是问题：

链接： https: //leetcode.com/problems/happy-number/

问题：

编写一个算法来确定一个数字是否“快乐”。快乐数字是通过以下过程定义的数字：从任何正整数开始，用其数字的平方和替换该数字，并重复该过程，直到该数字等于 1（它将停留在该位置），或者循环在不包括 1 的循环中无限循环。此过程以 1 结尾的数字是快乐数字。

例子：

输入：19

输出：真

解释：

1^2（1的平方）+ 9^2 = 82

8^2 + 2^2 = 68

6^2 + 8^2 = 100

1^2 + 0^2 + 0^2 = 1

这是代码：

class Solution(object):
    def isHappy(self, n):
        #getnext function will compute the sum of square of each digit of n
        def getnext(n):
            totalsum = 0
            while n>0:
                n,v = divmod(n,10)
                totalsum+=v**2
            return totalsum
        #we declare seen as a set to track the number we already visited
        seen = set()
        #we stop checking if: either the number reaches one or the number was visited #already(ex.a cycle)
        while n!=1 and (n not in seen):
            seen.add(n)
            n = getnext(n)
        return n==1

注意：如果我需要解释代码的工作原理，请随时告诉我

时间复杂度分析：

时间复杂度：O(243 * 3 + logN + loglogN + log loglog N)...=O(logN)。

查找给定数字的下一个值的成本为 O(log n)，因为我们正在处理数字中的每个数字，而数字中的位数由 logN 给出。 我的疑问：为什么数字的位数是logN？这里的N是什么？特定数字的值还是其他什么？

为了计算出总时间复杂度，我们需要仔细考虑链中有多少个数字以及它们有多大。

上面我们已经确定，一旦一个数字低于243，它就不可能再回到243以上。因此，根据我们非常浅薄的分析，我们可以肯定，一旦一个数字低于243，它就不可能再回到243以上。超过另外 243 个步骤才能终止。

每个数字最多有 3 位数字。经过更多的分析，我们可以将 243 替换为低于 243 的最长数字链的长度，但是因为该常数无论如何都不重要，所以我们不会担心它。 我的疑问：我认为上面一段与243*3的时间复杂度部分有关，但我无法理解为什么我们将243乘以3

对于大于 243 的 n，我们需要考虑链中大于 243 的每个数字的成本。通过一些数学计算，我们可以表明，在最坏的情况下，这些成本将为 O(log n) + O(log log n) + O(log log log N)...对我们来说幸运的是，O(logN) 是主要部分，而其他部分相比而言都很微小（总的来说，它们加起来小于 logN），所以我们可以忽略它们。我的疑问：对于 n 高于 243 的 O(log log n) O(log log log N) 背后的推理是什么？

Answer 1

嗯，我对第一个疑问的猜测是，以 10 为底的数字的位数是由它的值 (N) 取以 10 为底的对数并向下舍入得出的。例如，1023 将有floor(log10(1023))数字，即 3。所以，是的，N 是该数字的值。时间log复杂度表示对数，而不是具体以 2 或 e 为底的对数。

至于第二个疑问，可能与将数量减少到243以下所需的工作有关，但我不确定。一旦我解决了这个问题，我就会编辑这个答案。