計算運行程序的時間（大O符號）

Question

void foo(float[] array, int start, int end){ 
    if((end-start) <=1) return; 

    int x = (end-start)/5; 
    int y = 2*x; 
    int z = 4*x; 

    foo(array,start,start+y); 
    for(index = y; index < z; index++){ 
     array[index]++; 
    } 
    foo(array, start+z, end); 
} 

我得到的for循環的初始化被執行N + 1次，而內部碼被執行N次，則意味着時間複雜度將是O（（N +1）*（N））= O（n^2）。但是在這種情況下如何計算N？我該如何處理遞歸調用？我怎樣才能將這些信息轉換成Big O符號？

請不要說這是一個重複的問題。我明白，其他例子也存在類似的問題，但這個例子對我來說是抽象的，學習如何解決這個問題會在很多其他情況下幫助我。

Answer 1

假設輸入到foo是：

foo(array, 0, 1000) 

所以，首先，x變成200這是整個數據的五分之一。然後y和z成爲第二個和第四個quintiles。請注意，它們仍然是end - start（1000）的一部分，而不是常數。

的for雲：

for(index = y; index < z; index++) 

其是從y到z。 y爲400（2 * 1000/5），z爲800（4 * 1000/5）。所以for循環的次數是800 - 400 = 400 =（4 - 2）* 1000/5。也許分析這個給你的人稱它爲N，但這很荒唐。你在循環中做的是一個簡單的增量，它需要一個固定的時間（O(1)），並且沒有涉及到N！

所以讓我們自己命名。我會打1000以上的N。所以基本上，for循環2N/5次。

---

遞歸怎麼樣？第一次遞歸在start至start + x（即數據的前2/5）上遞歸，第二次遞歸在start + z至end（即，數據的最後1/5）上遞歸。

假設你的函數接受f(N)時間總共計算不管它是幹什麼的，它可以被分解爲：

f(N) = f(2N/5) + 2N/5 + f(N/5) 

現在，所有你需要的是分析這個遞歸函數，並嘗試瞭解什麼是命令。

---

雖然有很多方法來理解這一點，比如畫一個樹，顯示瞭如何f擴張和什麼參數，你也可以嘗試找到該功能的更容易上限和下限。如果它們是相同的，你很幸運：

2N/5 + 2*f(N/5) < f(n) < 2*f(2N/5) + 2N/5 

通過the master theorem，既限制落在案例3，並且兩個極限值練得θ(N)，所以你foo功能其實θ(N)。

的另一種方式也看它是以下內容：

1. 第一遞歸觸摸數據
2. for循環觸摸數據的所述第二2N/5的第一2N/5
3. 第二次遞歸觸及最後N/5個數據

正如你所看到的，數組的每個元素只被觸及一次。所以該函數的時間複雜度爲θ(N)。

Answer 2

在我們查看整個函數的實際Big-O之前，讓我們快速更正您的代碼片段。

// O(4 + N + 2*O(?)) = O(N + O(?)) 
void foo(float[] array, int start, int end){ 
    if((end-start) <=1) return; // O(1) 

    int x = (end-start)/5; // O(1) 
    int y = 2*x; // O(1) 
    int z = 4*x; // O(1) 

    foo(array,start,start+y); // O(?) 
    for(index = y; index < z; index++){ // O(N) 
     array[index]++; // O(1) 
    } 
    foo(array, start+z, end); // O(?) 
} 

現在，在基礎案例（end - start <= 1），FOO立即返回，使得它O(1)。在第二個基本情況下，這意味着此功能是O(N)（只是for循環）。在第三種情況下，這意味着該功能是O(N + N + N) = O(3N) = O(N)。它以這種方式進行。

重要的是要記住，我們忽略了一些（可能很大）的常量因子，但算法整體仍然屬於O(N)的類別。

不可否認，這種方法缺乏嚴謹性，但卻以最少的工作獲得了很好的估計。