您是如何计算的二进制搜索算法的大哦？ [英] How do you calculate the big oh of the binary search algorithm?

问题描述

我要寻找的数学证明，不只是答案。

I'm looking for the mathematical proof, not just the answer.

推荐答案

二叉搜索的递推关系是的（在最坏的情况下）

The recurrence relation of binary search is (in the worst case)

T(n) = T(n/2) + O(1)

使用硕士定理

• n是问题的大小。
• 一个是在递归子问题的数目。
• N / B为每个子的大小。 （这里假定所有的子基本上相同的尺寸。）
• F（n）是递归调用外面所做的工作，其中包括将所述问题和合并的解决方案，以子问题的成本的成本的成本。

下面一个= 1时，b = 2和F（N）= 0（1）[常量]

Here a = 1, b = 2 and f(n) = O(1) [Constant]

我们有f（N）= O（1）= O（N ^{登录<子> B A} ）

We have f(n) = O(1) = O(n^log_ba)

=> T（N）=为O（n ^{登录<子> B A} 登录 ₂ N））= O（日志<子> 2 N）

=> T(n) = O(n^log_ba log₂ n)) = O(log₂ n)

这篇关于您是如何计算的二进制搜索算法的大哦？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！