使用大 O 符号分析伪代码 complexity/runtime

Question

我需要一些帮助来解决问题。我刚开始阅读有关 O-notation 的内容，但在分析代码方面我还是个新手。

问题来了：

给出如下伪代码，其中A是一个数字字段，可以访问索引1到length(A)范围内的元素

1: procedure Adder(A)
2:      for i <- 1 to length(A)
3:          for j <- length(A) to 1 do 
4:              if i ≠ j then
5:                 A[i] <- A[i] + A[j]

用大 O 表示法给出以下代码行的复杂性：

第 4-5 行
第 3-5 行
第 2-5 行

所以对于第 4-5 行，我认为它应该是简单的 O(1)，因为它只是添加了 2 个元素。

其他两个我真的不确定。

对于第 3-5 行，我认为它应该是 O(n)，其中 n 是数字字段中的索引数。

最后对于第 2-5 行我会说它是 O(n^2) 因为我们现在必须循环？

Answer 1

这对我来说似乎是正确的，尽管你可能想重新表述你的一些理由

lines 4-5 I thought it should be simply O(1) since it simply just adds 2 elements.

它是 O(1) 因为 无论输入是什么，算法最终将执行 1 条或 2 条指令。它永远不会大于 1 或 2

finally for lines 2-5 I would say it's O(n^2) since we now have to loops?

它是 O(n^2)，因为嵌套循环正在迭代您作为输入的序列。不管发生什么，如果输入的长度为 N，则您将不得不进行 N 次循环，并在内部进行 N 次循环。所以你最终得到 N * N ，这是你建议的 N^2 。

使用大 O 符号分析伪代码 complexity/runtime

Analysing complexity/runtime of pseudocode using big-O notation

big-o

pseudocode