3

我在执行有关运行时间的任务时遇到问题。

问题陈述是：“Isabel 有一种有趣的方法来对包含 n 个整数的数组 A 中的值求和，其中 n 是 2 的幂。她创建了一个大小为 A 一半的数组 B，并设置 B[i] = A[2i] + A[2i+1]，对于 i=0,1,…,(n/2)-1。如果 B 的大小为 1，则输出 B[0]。否则，她将 A 替换为B，重复这个过程。她的算法的运行时间是多少？

这会被认为是 O(log n) 还是 O(n)？我在想 O(log n) 因为你会继续将数组分成两半，直到你得到最终结果，我相信 O(log n) 的基础是你不遍历整个数据结构。但是，为了计算总和，您必须访问数组中的每个元素，因此我认为它可能是 O(n)。任何帮助理解这一点将不胜感激。

4

2 回答 2

2

正如您自己发现的那样，您确实需要访问所有元素来计算总和。所以你的提议：

我相信 O(log n) 的基础是你不遍历整个数据结构

不成立。您可以放心地忽略算法存在的可能性O(log n)。

至于是O(n)或不同的东西，你需要考虑作为一个整体会完成多少操作。George Skoptsov 的回答很好地暗示了这一点。我只想提请注意一个事实（根据我自己的经验），要确定“运行时间”，您需要考虑一切：内存访问、操作、输入和输出等。在您的简单情况下，只有查看访问（或总和的数量）可能就足够了，但在实践中，如果您不从各个角度看待问题，您可能会得到非常倾斜的结果。

于 2013-02-25T23:38:18.973 回答
2

我相信 O(log n) 的基础是你不遍历整个数据结构。

没有信仰或猜测的基础。在心里运行算法。A大小数组将有多少次递归n？每次递归将有多少个求和（当数组 A 的大小为 时n）？

  • 第一次运行：n/2求和，n访问元素A
  • .
  • .
  • .
  • 最后一次运行：1求和，2访问元素A

总共有多少次运行？总结一下，什么是最高的幂n？

于 2013-02-25T23:39:52.993 回答