我在关于运行时间的任务上遇到问题。总结整数的算法的运行时间
问题陈述是： “伊莎贝尔有一个有趣的方式来总结n个整数的数组A中的值，其中n是2的幂，她创建了一个A的一半大小的数组B，对于i = 0,1，...，（n/2）-1，设B [i] = A [2i] + A [2i + 1]，如果B的大小为1，则输出B [0] ，她用B代替A，然后重复这个过程，她算法的运行时间是多少？“
这会被认为是O（log n）还是O（n）？我在考虑O（log n），因为你会继续将数组分成一半，直到得到最终结果，我相信O（log n）的基础是你不遍历整个数据结构。然而，为了计算总和，你必须访问数组中的每个元素，这使我认为它可能是O（n）。任何帮助理解这将不胜感激。
当你想出你自己，你确实需要访问所有元素来计算总和。所以，你的主张：
我相信O（log n）的基础是，你不遍历整个数据结构
不成立。那么您可以放心地忽略当时算法为O(log n)的可能性。
至于O(n)或者其他不同的东西，你需要考虑整个做多少个操作。 George Skoptsov's answer给出了一个很好的暗示。我只想提醒注意一个事实（根据我自己的经验），要确定“运行时间”，您需要考虑所有因素：内存访问，操作，输入和输出等。在您的简单情况下，仅限于查看访问次数（或总和数量）可能就足够了，但实践中，如果不从各个角度来看待问题，结果可能会出现偏差。
我相信O（log n）的基础是你不遍历整个 数据结构。
没有信仰或猜测的基础。精神上运行该算法。 对于n大小的数组A会有多少次递归？ 每次递归有多少总和（当数组A的大小为n）？
n/2求和，n访问的A1总和，2访问的A元素有多少运行在那里总？当你总结这个时，n的最高功率是多少？
这显然是家庭作业......我认为我们应该避免给这些问题明确的答案。 – 2013-02-25 23:43:44
@GeorgeSkoptsov我同意，我认为你的回答比我的好。关于如何处理作业问题的meta已经有很多讨论，并且我记得读到它们应该像普通问题一样对待。但我可能会误解（或政策可能已经改变） – mgibsonbr 2013-02-25 23:48:28
呵呵，我没有遵循meta ...我不同意这个政策。我可以理解帮助某人解决问题的方法，但不能将解决方案提供给明确要求自己推导出来的人。 – 2013-02-25 23:57:48