计算运行程序的时间（大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)的类别。

不可否认，这种方法缺乏严谨性，但却以最少的工作获得了很好的估计。