O notation of a Loop
This question already has an answer here:
You just have to count the total number of iterations:
1 + 2 + 3 + .. + n - 1 = n * (n - 1) / 2
as you correctly inferred. When you replace n with log(n) , just do the same in the final formula, which then becomes log(n) * (log(n)+1) / 2 , or in Big-O notation, O((log(n))^2) .
If the condition of the outer loop is changed to i < log(n) then the overall complexity of the nested two-loop construct changes from O(n2) to O(log(n)2)
You can show this with a simple substitution k = log(n) , because the complexity of the loop in terms of k is O(k2). Reversing the substitution yields O(log(n)2).
For nested for loops (when using the O notation, ofc) you can multiply the worst-case scenario of all of them. If the first loop goes to x and you have a nested loop going to i (i being at worst-case x) then you have a run-time complexity of O(x^2)
链接地址: http://www.djcxy.com/p/39358.html上一篇: Find（）函数的复杂性是什么？
下一篇: O循环的符号