algorithm - 大概是简单的运行时分析，需要解释

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 为底的对数仅相差一个常数系数。