二分查找运行时间上界：Recurrence Relation

Question

我试图理解一个典型的二进制搜索算法具有 运行ning 时间 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(n) = T(2^(log n)) <= T(2^(ceil(log n))) 使用 T 是非递减的事实。