假设我有这样的算法:
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) 的？还是我完全错了？
注意:我无法将两个循环合二为一。他们执行最终进入递归调用的操作。你能想到的任何其他东西都是不允许的。这个问题有很多限制条件。
最佳答案
如果您真的在寻找 O(x) + O(y) = O(x+y) 的证明，它可以按照以下方式工作:
R1 ∈ O(x) ∧ R2 ∈ O(y)
⇒ ∃ R1 < ax ∧ ∃ b。 R2 < 由
⇒ ∃ a, b。 R1 < ax ∧ R2 < by
⇒ ∃ a, b。 R1+R2 < 斧 + 由
⇒ ∃ a, b。 c=max(a,b) ∧ R1+R2 < cx + cy
⇒∃c。 R1+R2 < c(x+y)
⇒ R1+R2 ∈ O(x+y)
关于algorithm - 递归关系 : Proving (n/2) + (n/2) = O(n)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/13181613/