O循环的符号
这个问题在这里已经有了答案：
你只需要计算迭代的总次数：
1 + 2 + 3 + .. + n - 1 = n * (n - 1) / 2
正如你正确推断的那样。 当用log(n)替换n时，只需在最终公式中做相同的处理，然后变成log(n) * (log(n)+1) / 2 ，或者用Big-O表示法O((log(n))^2) 。
如果外循环的条件变为i < log(n)那么嵌套双循环结构的整体复杂度从O（n2）变为O（log（n）2）
你可以用一个简单的替换k = log(n)来显示它，因为循环的复杂度k是O（k2）。 反转替代产生O（log（n）2）。
对于嵌套for循环（当使用O符号，ofc时），你可以乘以所有这些的最坏情况。 如果第一个循环转到x，并且有一个嵌套循环转到i（我处于最坏情况x），那么您的运行时复杂度为O（x ^ 2）
链接地址: http://www.djcxy.com/p/39357.html上一篇: O notation of a Loop
下一篇: How can I learn if an algorithm runs in O(n) time, or O(nlogn)?