根据今天的讲座,第一个循环的运行时间为 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)
}
有人可以详细说明原因吗?
最佳答案
第一个循环将精确地执行一个常数时间操作 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 为底的对数仅相差一个常数系数。
关于algorithm - 大概是简单的运行时分析,需要解释,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/21318264/