快乐数程序使用数组,帮我计算时间复杂度?

Happy number program using array, help me how to calculate Time Complexity?

我用数组写了一个快乐数字程序,请问如何计算时间复杂度?如果在用等于其所有数字的平方和的数字反复替换它之后,将我们引向数字“1”,则任何数字都将被称为快乐数字。所有其他(不快乐的)数字永远不会达到“1”。相反,他们将陷入不包括“1”的数字循环中。

def happy(num):
    ls = []
    result = 0
    while True:
        result = sqr_digits(num)
        if result == 1:
            return True
        elif result in ls:
            return False  # not happy
        else:
            ls.append(result)
            num = result

def sqr_digits(num):
    result = 0
    while(num > 0):
        digit = num % 10
        result += digit ** 2
        num //= 10
    return result

    num = 145
    print(happy(num))

[注意:在回答问题时,我忘记了您的代码使用的是digit^2,但我只是提供了基于digit的解决方案。复杂度计算机制相同。如果您阅读答案,您可以轻松地自己找出 digit^2 的复杂性。当我有时间时,我会更新答案。希望你不介意]

嗯,如果有一个数字 n(base 10),那么它最多可以有 log10(n) + 1 个数字。我希望,我不会解释它...只是 google 它 how many digits in a 10 based number and how to find it using log.

现在,让我们解释一下所提供算法的复杂性:

算法只有在和变为个位数时才会停止。

所以,我们可以计算位数,我们必须添加,这就是最终的复杂性。

不可能准确计算该算法的复杂度,但我们可以计算最坏情况下的复杂度...3 digits,当然 999 的最大数是多少,所以我们将始终在 d digits 个数字中考虑 d nines

1st iteration:: no of digits, d1 = log10(n) + 1, and n1 = d1*10, (originally d1*9 in worst
case, but we're taking much worse and the reason is to calculate complexity properly)


2nd iteration:: no of digits, d2 = log10(n1) + 1 and n2 = d2*10
                                 = log10(d1*10) + 1
                                 = log10(d1) + 1 + 1 (cause, log(a*b) = log(a)+log(b))
                                 = log10(log10(n) + 1) + 1 + 1


3rd iteration:: no of digits, d3 = log10(log10(log10(n)+1)+1) + 1 + 1 + 1

...
...

我想,你可以看到这是怎么回事。总位数可以写成:

total digits = d1 + d2 + d3 + ....

By removing the 1 inside log's(for simplification) we can write simply:
total digits = log10(n) + 1 + log10(log10(n)) + 2 + log10(log10(log10(n))) + 3 + ...

but, log10(n) + 1 >>> log10(log10(n)) + 2

所以,我们可以看出最终的复杂度是由log10(n)决定的。最终的复杂度是:

complexity = c * log10(n) // here is "c" a constant such that c * log10(n) > total digits
which
we can say O(log10(n))

希望您已经正确理解了这个概念...