python - 这个函数的大 O 是多少？

Question

def fd(n):
    x,y,count1,count2 = n,1,0,0
    while (x > 1): (x,count1) = (x/5,1+count1)
    while (y < n): (y,count2) = (count1+y,1+count2)
    return count2

Answer 1

让我们来看看。第一个循环计算n可以除以 5 的次数，count1log(n) 也是如此（常数不计入 O() 计算）。然后第二个循环计算多少次count1(= log(n)) 可以加到 1 到n，所以它基本上循环 n / log(n) 次。

在我看来这是 O(log(n) + (n/log(n)))。

正如 JF Sebastian 指出的那样，n/log(n) 支配 log(n)，所以最终答案应该是 O(n/log(n))。

Answer 2

I want to point out that the answer to this question depends on an agreement about what we are talking about (is important the fact that double numbers are going to be manipulated? do you want a theoretical answer that could sound unsatisfactory or a practical answer?)

Please, let me rephrase this answer: https://stackoverflow.com/a/2027842/512225 :

People play a bit fast and loose with big-O notation.

Algorithmic complexity, and hence big-O notation, should be stated in terms of the size in bits of the input, not in terms of the values of the input. Assuming binary input and arbitrarily-large numbers, and N the number of bits of input, N = log(n). The complexity is O(exp(N)/N) = O(exp(N)/N) since the second loop requires n/log(n) steps = exp(N)/N steps.

In practice it makes sense to talk about complexity as though N were the input itself, not the size of the input. In that case the complexity of your function is n/log(n).

Anyway we are disregarding the issues given by the fact that n is limited by the definition of double, so that strictly speaking it does not make sense to talk about the asymptotic behavior (with n -> infinity). And we disregard also the fact that if your input is a double them its size is constant and so the complexity of your algorithm is (strictly speaking) O(1) (huge_constant times 1) with huge_constant equal to worst case time (that constant probably depends on the largest number you can express with Python's doubles).

Summarizing:

the formal answer is O(1) but O(exp(N)) is not that bad as answer, O(n/log(n)) is a good answer too (and probably what you really need).