您是如何计算的二进制搜索算法的大哦？

本文介绍了您是如何计算的二进制搜索算法的大哦？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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(nlogba)

=> T（N）=为O（n 登录 B A 登录 2 N））= O（日志 2 N）

=> T(n) = O(nlogba log2 n)) = O(log2 n)