time-complexity - 如何解决给定代码块示例的 O-Notation？

Question

我正在为我的算法考试进行修改，遇到了一个我不明白的问题，如何解决它。这是示例；

for (m=0; m<n; m++)
       for (i=1; i<m; i=2*i)  
          [Sequence, Run Time O(1)]

我发现了直观的 O(n^2) 但我不确定它是否属实。如果你们能向我解释一下，我会很高兴的。再次感谢！

标签： time-complexitybig-o

Answer 1

虽然 O(n^2) 是一个上限，但它并不是你能想到的最严格的。该标题转到 O(nlog(n))。希望很清楚内部循环运行 log(m) 次。所以你得到的是函数的总运行时间是 log(1) + log(2) + ... + log(n)。因为对于所有 i <= n，我们有 log(i) <= log(n)，并且总和中有 n 项，我们得到总和以 nlog(n) 为界。