以下两个重复的复杂性是否相同？

Question

我有两个递归关系：

T(n) = T(n/2) + c       // complexity O(logn)

T(n) = 2T(n/2) + c      // is the complexity O(logn)????

c 在这两种情况下都是一个常量，即我们在递归的合并部分进行持续工作。

第一个循环是二进制搜索，我们不断丢弃数组的一半。

假设第二次递归从未排序的数组中找到最大元素，我们在每个步骤中将数组分成两部分，然后比较每个部分的结果以给出单个最大值。

在第一种情况下，我们没有遍历整个数组。在第二个中，我们正在遍历整体。现在，如果我为两者构建一个递归树，我将得到 O(logn) 的复杂性，因为两棵树的高度相同。如果我错了请纠正我。这是我的困惑，所以请帮助我解决它。

Answer 1

它不是相同的复杂性。第二个类似于 O(n)

一个简单的方法是修复 c = 0 和 T(1) = a（a 是常数）。

然后：

T(2) = 2T(1) = 2a
T(4) = 2T(2) = 4a
T(8) = 2T(4) = 8a
...
T(n) = n*a

您可以看到线性复杂度。