这个函数的时间复杂度为O(log(n))。为什么?难道它不是循环到n吗?
function fxn($n) {
for ($i = 1; $i <= $n; $i *= 2)
echo $i;
}
顺便说一下,我对O(n)分析还不太熟悉。 不过这个函数看起来确实是O(n),因为它循环了n次。
function fxn($n) {
for ($i = 1; $i <= $n; $i *= 2)
echo $i;
}
顺便说一下,我对O(n)分析还不太熟悉。 不过这个函数看起来确实是O(n),因为它循环了n次。
它没有循环遍历所有元素,在每一步中,它会跳过前一步元素的两倍 - 因为 $i *= 2
部分。也就是说,假设 $i
的初始值大于零,否则它将是一个无限循环:因为它的写法,$i
总是等于 0
。
n
,但不是按照一(或任何固定值),否则就会成为O(n)。
这是它的作用: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| | | | |
+--+-----+-----------+-----------------------+
Steps 1 2 3 4
lg(128) = 7 (lg = log in base 2)
= 8 - 1
- 1
是一个常数,因此它不会影响我们的运行时间计算。这个循环的时间复杂度为O(n):
function fxn($n) {
for ($i = 0; $i <= $n; $i++)
echo $i;
}
因为$i
取以下值:
1, 2, 3, 4, 5, 6, 7, ..., n
function fxn($n) {
for ($i = 1; $i <= $n; $i *= 2)
echo $i;
}
$i
会取以下值:1, 2, 4, 8, 16, 32, 64, ..., n
O(1)
,因为它运行的次数是恒定的。 - fanjavaidn
次。随着n
的增长,循环的迭代次数也增加。如果n
是10亿,则循环运行10亿次。这是标准的O(n)
操作。 - john_science