我想知道以下每个语句的大 O 表示法是什么:
Sum = 0;
for i=1 to N^2 do:
for j=1 to N do:
'Sum += 1;
当Sum = 0时,它肯定是O(1),因为它只会被执行一次。但是第二个语句让我感到困惑,它应该是O(N)吗?因为这是第一个循环?还是应该是O(N^2),因为N^2是关于变量N的二次函数?
第一个循环的时间复杂度为O(N2),因为它执行了N2步。每一步都会执行内部循环,其中包含N个步骤,因此总共有N2 * N或N3个步骤,算法的时间复杂度为O(N3)。
您将会对N进行三轮循环…所以我说:O(n^3)
算法:
Sum = 0; ~ 1
for i=1 to N^2 do: ~ 1+2N^2
for j=1 to N do: ~ (1+2N) * N^2
'Sum += 1; ~ 1 * N * N^2
时间复杂度:
Time = 1 + 1+2N^2 + (1+2N)*N^2 + 1 * N * N^2
Time = 2 + 2N^2 + N^2 + 2N^3 + N^3
Time = 2 + 3N^2 + 3N^3
O(Time) = O(2 + 3N^2 + 3N^3) ~ O(N^3)
1+2N^2
这个术语很好奇,乘数 2 是从哪里来的?另外,当涉及到下一行 (1+2N) * N^2
时,那不应该是 (1+2N^2) * N
吗? - Jonathan Leffler
O(1)
。如果他们正在分析加法算法,则情况并非如此。我相信CLRS算法分析介绍了这些假设。另一种表达方式是,您确定硬件级别的位翻转是O(1)
吗?在哪些电路上? - rliu