algorithm - 二分查找运行时间上限 : Recurrence Relation

Question

我试图理解典型二分搜索算法的运行时间为 O(log n) 的证明。在这个证明中，确定了一些输入大小 n 的一般运行时函数 T(n)，这用于显示大 O。我了解其中的大部分，但不是第一步。

证明首先确定如果 n=0 运行时间是常数，否则 T(n) <= c + T(floor(n/2))对于一些常数 c。这对我来说很有意义。然后证明说明函数 T(n) 是非递减的，这对我来说也很有意义。

但随后它会尝试找到满足两个不等式的上限(对于 n = 0 和 n != 0)。它通过使用 T(n) 不递减这一事实来确定 T(n) <= T(2^{ceil(log n)}) 来实现这一点。这是我不明白的部分。这个界限从何而来？为什么要选择那个特定的不平等？我看不到它的来源。

Answer 1

因为我们有:

• n = 2^log(n)
• log n <= ceil(log n)
• 2^(log n) <= 2^(ceil(log n))

利用 T 不递减这一事实，我们可以得出 T(n) = T(2^(log n)) <= T(2^(ceil(log n))) 的结论。