難道我們真的有情況下，這種算法

-6

我有解決以下算法難道我們真的有情況下，這種算法

enter image description here

現在首先我的問題的運行時間的麻煩，是這裏的情況很重要（我不能拿出與2個不同的輸入相同的大小，彼此不同）？

其次，我認爲這個算法運行在O(n^2)。我對嗎？

來源

2014-02-07 Hamed Minaee

我不知道爲什麼這個問題得到-4分，我甚至想出瞭解決方案，並要求幫助 –

因爲它有點偏離主題，而且你沒有表現出對問題的任何理解。你來了多遠？你有什麼想法？ etc. – OBu

它只是作業轉儲 – zvisofer

你寫了// @ OBU的答案的評論是大約只有四分之一的權利： 1 * N + 2 *（N-1）+ 3 *（N-2）+ ... + N * 1

即等於：

薩姆（I = 1 ... N，我*（N-1 + 1））= N *薩姆（ⅰ） - 總和（I * I）+ N = N * [ n（n + 1）/ 2] - [n（n + 1）（2n + 1）/ 6] + n

如果需要，可以自由計算精確公式，但總體複雜度爲O ñ^ 3）。作爲一個經驗法則（更像是我回憶起來的一個後臺計算技巧......只是爲了給你一個快速的想法）：如果你不確定使用多個for的算法（with不同的長度，但都與n相關，如上所述）嘗試計算在算法中間執行多少操作（n/2）。這通常會給你一個關於整個事情的運行時間複雜性如何的想法 - 你基本上是計算總和中的最大元素，所以總體複雜度總是> =而不是你計算的東西（在大多數情況下，它是同樣）。

來源

2014-02-07 03:49:02

只給你一些提示：

多少圈你有和他們如何拼圖？
每個循環運行的頻率如何（從外部到內部循環開始解決這個問題）
如果有疑問，請嘗試n = 4或5並計算每個步驟。之後，你會對發生的事情有一個很好的感覺。

來源

2014-02-07 00:26:35 OBu

是的，我做到了讓我解釋我到現在爲止：我試着用不同的數字，我明白，當外環的每次迭代中，當中間循環上去內循環在K去所以我得到這個公式：1 * n + 2 *（n-2）+ ... + n *（1）=它是n *（1 + 2 + 3 + ...）= n（n + 1）/ 2但我仍然不確定自己是否正確，因爲通常情況下我會得到O（n^3）類似的情況，而且我更重要的問題是我們是否真的需要在這裏提供案例？ –

難道我們真的有情況下，這種算法

回答

相關問題