用大O表示法分析伪码的复杂度/运行时
用大O表示法分析伪码的复杂度/运行时
提问于 2019-04-09 09:28:33
我需要一点帮助来解决问题。我刚刚开始阅读关于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]用大-O表示法给出以下代码行的复杂性：
- 第4-5行
- 第3-5行
- 第2-5行
因此，对于第4-5行，我认为它应该是简单的O(1)，因为它只是添加了2个元素。
对另外两个人我真的不确定。
对于第3-5行，我认为应该是O(n)，其中n是数字字段中的索引数。
最后，对于第2-5行，我会说它是O(n^2)，因为我们现在必须循环？
回答 1
Stack Overflow用户
回答已采纳
发布于 2019-04-09 09:42:34
这在我看来是正确的，尽管你可能想要重新表述一下你所拥有的理由。
第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。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/55589461
复制相关文章
相似问题
腾讯云开发者
