什么是主定理？如何使用该定理得出二进制搜索的时间复杂性？我想知道这个话题的确切解释。提前谢谢！
主定理提供了一种明确的方法来确定各种具有大θ符号的分治算法的运行时间(给出了最坏情况下运行时间的严格上限和下限(。许多分治算法在大小为n的输入上的运行时间可以用递推方程T(n(来表示。假设我们有：
- 对于足够小的输入，T(n(是常数
- 对于足够大的输入，T(n(=a*T(n/b(+f(n(，其中a是递归调用算法的子问题的数量，每个子问题的大小为n/b，非递归开销的总量为f(n(。非递归开销是算法在除法步骤和征服步骤中花费的开销
现在，还考虑一个关键函数：n^(log_b(a((，也就是说，n是a的对数基数b的幂。给定递推方程，你可以计算出这是什么，因为你知道a和b是什么。
主定理本质上说：
- 如果f(n(多项式小于n^(log_b(a((，则算法在时间上与n^(log _b(a((成比例运行
- 如果f(n(=n^(log_b(a((，则算法在时间上与n^(log _b(b((*log(n(成比例运行
- 如果f(n(多项式大于n^(log_b(a((，则该算法在时间上与f(n(成比例运行
请注意，并非所有的分治算法都有运行时间，对于一些a、b和f(n(，这些运行时间可以用这种形式表示，但其中很多都可以，包括二进制搜索。
二进制搜索采用大小为n的输入，将中间元素与搜索到的元素进行比较会花费大量的非递归开销，将原始输入分成两半，并且只在数组的一半上递归。现在将其插入主定理，其中a=1，大小为n/b的子问题，其中b=2，非递归开销f(n(=1。计算临界函数n^(log_b(a((=n^(log _2(1((=n ^0=1。现在我们将f(n(=1与临界函数n^(log_b(a((=1进行比较。它们是相等的，所以我们在主定理的情况2中。因此，总运行时间与n^(log_b(a((*logn=logn成比例。