What is the time complexity of my function?
This question already has an answer here:
The outer loop runs n times.
For each iteration, the inner loops runs n / i times.
The total number of runs is:
n + n/2 + n/3 + ... + n/n
Asymptotically (ignoring integer arithmetic rounding), this simplifies as
n * (1 + 1/2 + 1/3 + ... + 1/n)
This series loosely converges towards n * log(n) .
Hence the complexity is O(N.log(N)) as you expected.
The first inner loop runs n times
The second inner loop runs n/2 times
The third inner loop runs n/3 times
.. The last one runs once
So n + n/2 + n/3 + ... + 1 = n(1+1/2+1/3+1/4 + ... +1/n) .
This is n multiplied by the sum of harmonic series, which does not have a nice closed form representation. But as shown here it is O(log(n)) . So overall the algorithm is O(n log(n))
As an alternative, use a variable substitution y = n - x followed by Sigma notation to analyse the number of iterations of the inner while loop of your algorithm.
The above overestimates, for each inner while loop, the number of iterations by 1 for cases where n-1 is not a multiple of i , ie where (n-1) % i != 0 . As we proceed, we'll assume that (n-1)/i is an integer for all values of i , hence overestimating the total number of iterations in the inner while loop, subsequently including the less or equal sign at (i) below. We proceed with the Sigma notation analysis:
where we, at (ii) , have approximated the n :th harmonic number by the associated integral. Hence, you algorithm runs in O(n·ln(n)) , asymptotically.
Leaving asymptotic behaviour and studying actual growth of the algorithm, we can use the nice sample data of exact (n,cnt) (where cnt is number of inner iterations) pairs by @chux (refer to his answer), and compare with the estimated number of iterations from above, ie, n(1+ln(n))-ln(n) . It's apparent that the estimation harmonize neatly with the actual count, see the plots below or this snippet for the actual numbers.
Finally note that if we let n->∞ in the sum over 1/i above, the resulting series is the infinite harmonic series, which is, curiously enough, divergent. The proof for the latter makes use of the fact that in infinite sum of non-zero terms naturally is infinite itself. In practice, however, for a sufficiently large but not infinite n, ln(n) is an appropriate approximation of the sum, and this divergence is not relevant for our asymptotic analysis here.
链接地址: http://www.djcxy.com/p/39342.html
上一篇: 什么是时间复杂性以及如何找到它？
下一篇: 我的功能的时间复杂度是多少？