sum = 0;
for(int i = 0; i < N; i++)
for(int j = i; j >= 0; j--)
sum++;
据我了解,第一行是1个操作,第二行是
(i+1)
个操作,第三行是(i-1)
个操作,第四行是n
个操作。这是否意味着运行时间将是1 + (i+1)(i-1) + n
?只是最后几步让我感到困惑。sum = 0;
for(int i = 0; i < N; i++)
for(int j = i; j >= 0; j--)
sum++;
(i+1)
个操作,第三行是(i-1)
个操作,第四行是n
个操作。这是否意味着运行时间将是1 + (i+1)(i-1) + n
?只是最后几步让我感到困惑。sum ++
这一行被执行的次数”,因为如果我们知道这个值,我们就知道算法中两个循环所花费的总时间。为了弄清楚这一点,让我们追踪一下这些循环发生了什么。在外部循环的第一次迭代中,i == 0
,所以内部循环将恰好执行一次(从0到0倒计时)。在外部循环的第二次迭代中,i == 1
,内部循环执行两次(首先是j == 1
,然后是j == 0
)。更一般地说,在外部循环的第k次迭代中,内部循环执行k + 1
次。这意味着最内层循环的总迭代次数由以下公式给出:1 + 2 + 3 + ... + N
N (N + 1) N^2 + N N^2 N
--------- = ------- = --- + ---
2 2 2 2
N^2 / 2
是支配增长项,因此如果我们忽略其常数因子,就会得到 O(N2) 的运行时间。sum++
这是一个单独的操作,不会重复。
for(int j = i; j >= 0; j--)
这个循环执行了i+1次。其中有几个操作,但你可能不需要计算asm指令的数量。因此,在这个问题中,我假设它是i+1的乘数。由于循环内容是单个操作,所以循环和其块执行了i+1个操作。
for(int i = 0; i < N; i++)
这个循环运行了N次。所以和之前一样,这是N的乘数。由于该块执行i+1次操作,因此该循环总共执行N(N+1)/2次操作。这就是答案!如果你想考虑大O复杂度,那么这可以简化为O(N2)。
它不是可加的:内部循环对于外部循环的每次迭代都会发生一次。因此,它是O(n2)。
顺便说一下,这是为什么我们使用渐近符号表示这种情况的好例子——根据“操作”的定义,计数的确切细节可能会有相当大的差异。(例如,sum++
是单个操作,还是 将 sum 加 1 并将结果存储到 temp 中;将 temp 加载到 sum 中
?)但由于我们知道所有这些可以隐藏在一个常数因子中,所以它仍然是O(n2)。
不,你不能为每行计算特定数量的操作然后将它们累加。像“for”这样的结构的整个意义在于使给定的代码行能够运行多次。你应该使用思维和逻辑技巧来确定“sum ++”这一行将以N的函数运行多少次。提示:它会在第三行被遇到的每一次运行一次。
第二行会遇到多少次?
每当第二行被遇到时,“i”的值都会被设置。第三行会运行多少次以该值?因此,它会运行多少次?(提示:如果我在几个不同的场合给了你不同金额的钱,你如何找出我总共给了你多少钱?)
每当第三行被遇到时,第四行会发生一次。
哪一行发生最频繁?它在N方面有多频繁?
所以你感兴趣的是sum++以及它被执行的次数。
最终的sum状态将给出你答案。
实际上,你的循环只是:
Sigma(n) n从1到N。
这等于:N*(N+1) / 2
这在大O符号表示法中为O(N^2)
此外,在你的算法中没有最坏情况的名称。
或者你可以说最坏情况是当N趋近于无穷大时。