为什么当替换t(1)代替复发算法时，我们可以推断出Big-O

Question

问题

我正在尝试找到算法的复杂性。该算法通过递归解决 size size n-1> n-1 的两个子问题，解决了大小 n 的问题/em>。

所以，我写了一个复发：

T(n) =   2 * T(n-1) + 1 * O(1)
     =   4 * T(n-2) + 3 * O(1)
     =   8 * T(n-3) + 7 * O(1)
     = 2^k * T(n-k) + ((2^k)-1) * O(1)

我在这一点上停留，因此我在Google上进行了一些搜索。大多数示例用 k 用 n-1 替换为 t（n-k）变为 t（1）。

T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1) // substitute k with n - 1

问题

之后，他们得出结论 big-o 的此复发是O(2^(n-1))。

我对此感到非常困惑。我不知道

（i）我仍然知道T(1)的复杂性，不是吗？

（ii）T(1)与结论和

有何关系

（iii）我们如何从此公式T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1)。

任何帮助都将不胜感激。

Answer 1

T(n) = 2^(n-1) * T(1) + ((2^(n-1))-1) * O(1) 

这里t（1）始终是恒定的。因为 T(n）是指对于k的某些较大值，输入大小n > k的时间复杂性。现在，如果n是一个常数，例如n = 5，则算法的时间复杂性是常数。因为要执行n = 5的算法，这将需要同一时间。

请记住，在时间复杂性中，我们测量功能的生长。现在，对于n的恒定值，生长是恒定的。对于此逻辑T(1) = constant。

这个想法已用于查找阵列的中位数。它将数组分为5个元素的块，然后声称每个块的排序是恒定的。因为大小是固定的。