arrays - 对整数求和的算法的运行时间

Question

我在一项关于运行时间的作业上遇到了麻烦。

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

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

Answer 1

I believe the basis of O(log n) is that you do not traverse the entire data structure.

没有任何信念或猜测的基础。在心里运行算法。对于大小为 n 的数组 A 会有多少次递归？每次递归(当数组 A 的大小为 n 时)会有多少求和？

• 第一次运行:n/2 次求和，n 次访问A 的元素
• >。
• >。
• .
• 上次运行:1求和，2访问A
的元素

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