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

Question

我用数组写了一个Happy number程序，请问如何计算时间复杂度？如果在用等于其所有数字的平方和的数字反复替换它之后，将我们引向数字“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 = resultdef sqr_digits(num):    result = 0    while(num > 0):        digit = num % 10        result += digit ** 2        num //= 10    return result    num = 145    print(happy(num))

Answer 1

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

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

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

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

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

精确计算该算法的复杂性是不可能的，但我们可以计算最坏情况的复杂性……最大数当然是3 digits，999所以我们总是考虑d nines一个d digits数字。

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))

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