我在關於運行時間的任務上遇到問題。總結整數的算法的運行時間
問題陳述是： 「伊莎貝爾有一個有趣的方式來總結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