0

所以说我有一个这样的算法：

void dummy_algorithm(int a[]) {
   int center = floor(a.length/2);
   //For reference purposes: Loop 1  
   for(int i = 0; i < center; i++) {
       //The best code you've ever seen
   }
   //Loop 2
   for(int j = center + 1; j < a.length; j++) {
      //Slightly less awesome code
   }
}

这是非常基本的东西。我知道两个循环都遍历数组的一半，从而给每个循环一个 (n/2) 复杂性。但是，该方法所做的总工作显然是 O(n)。

所以，我的问题是：我如何证明（通过递归关系）这个算法是 O(n)？还是我完全错了？

注意：我不能将两个循环合二为一。它们执行最终进入递归调用的操作。其他你能想到的都是不允许的。这个问题有很多限制。

4

3 回答 3

1

如果您真的在寻找O(x) + O(y) = O(x+y)的证明，它可以按照以下方式工作：

R1 ∈ O(x) ∧ R2 ∈ O(y)
⇒ ∃ a。R1 < ax ∧ ∃ b。R2 < 由
⇒ ∃ a, b。R1 < ax ∧ R2 < by
⇒ ∃ a, b。R1+R2 < ax + 由
⇒ ∃ a, b。c=max(a,b) ∧ R1+R2 < cx + cy
⇒ ∃ c。R1+R2 < c(x+y)
⇒ R1+R2 ∈ O(x+y)

于 2012-11-01T17:01:13.227 回答
0 
  (N/2) + (N/2)
= 2*(N/2)
= 2N/2
= N
于 2012-11-01T16:43:33.613 回答
0

时间复杂度（以及是否需要递归关系）取决于您在循环中所做的事情，即

//The best code you've ever seen (*complexity1*)

和

 //Slightly less awesome code (*complexity2*)

是。

如果每次迭代只需要固定的时间量，即复杂度1和复杂度2在O(1)中，那么总复杂度将是n*O(1) = O(n)。这显示了Big-O-Notation 的真正作用：从诸如复杂性1和复杂性2 等常量因素中抽象出来。

如果每次迭代都需要 O(f(n))，那么您的总时间复杂度将为 O(n*f(n))。

如果每次迭代都进行递归调用，即dummy_algorithm使用较小参数调用，则确实需要递归关系来计算时间复杂度。递归关系的外观取决于您进行递归调用的频率以及使用什么参数。http://en.wikipedia.org/wiki/Recurrence_relation向您展示了如何找到和解决适当的递归关系。

于 2012-11-01T16:50:29.303 回答