假设运行时分析简单,需要解释

Question

根据今天的讲座,第一个循环具有顺序的运行时O(n),而第二个循环具有顺序的运行时O(log(n)).

for (int i = 0; i < n; i++) { // O(n)
    stuff(); // O(1)
}

for (int i = 1; i < n; i*=4) { // O(log(n))
    stuff(); // O(1)
} 

有人可以详细说明原因吗？

Answer 1

第一个循环将完成一次恒定时间操作n.因此它是O(n).

第二个循环(从i = 1没有开始i = 0,你有一个我修复的拼写错误)执行它的主体i设置为1,4,16,64,...即4 ^ 0,4 ^ 1,4 ^ 2,4 ^ 3,......直到n.

4^k < n时k < log_4(n).因此,第二循环的主体执行O(log(n))时间,因为对数基数4和对数基数e仅相差恒定系数.