我正在尝试计算这个伪代码所代表的算法的时间复杂度:
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n / 6; j++)
sum = sum + 1;
我知道第一行会运行n次,但我不确定第二行。
我正在尝试计算这个伪代码所代表的算法的时间复杂度:
sum = 0;
for (i = 1; i <= n; i++)
for (j = 1; j <= n / 6; j++)
sum = sum + 1;
这里有一个简单的双重循环:
for i=1;i<=n;i++
for j=1; j<=n/6; j++
sum = sum + 1;
将被执行的次数),你会发现它是:
以大O符号表示,它是:n*n/6 = n²/6
因为我们不关心常数项,因为随着O(n²)
n
的增长,常数项是否存在都没有(大)区别!
n * (n / 6)
次操作:复杂度相同,但结果不同。 - chqrlie