使用big-O表示法分析伪代码的复杂性/运行时

Question

我需要帮助解决一个问题。我刚刚开始阅读有关O符号的内容，但在分析代码时我还是新手。

所以这就是问题所在：

给出以下伪代码，其中A是数字字段，其索引1到长度（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]

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

1. 第4-5行
2. 第3-5行
3. 第2-5行

因此，对于第4-5行，我认为它应该只是O（1），因为它只是添加了2个元素。

和其他两个我真的不确定。

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

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

Answer 1

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

第4-5行我认为它应该只是O（1），因为它只是添加了2个元素。

它是O（1）因为无论输入是什么，算法最终都会执行1或2条指令。它永远不会超过1或2

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

它是O（n ^ 2），因为嵌套循环正在迭代你输入的序列。无论发生什么，如果输入的长度为N，则必须进行N次循环，并在内部进行N次循环。所以你最终会得到N * N，这是你建议的N ^ 2。