Question

三分搜索算法的时间复杂度分析

三分搜索算法的时间复杂度分析，先将待查元素x与n/3处的元素比较，然后将x与2n/3处的元素进行比较。比较的结果或者找到x，或者将搜索范围缩小的原来的n/3，程序有，时间复杂度为O(3log3(n))，要求解释分析时间复杂度的详细过程，好的话会追加（不会的不要瞎说，求大神）

Answer 1

首先第一点 时间复杂度在用大O表示时常数是没有意义的,所以复杂度比较标准的写法是O(log n)

得到这个复杂度 由以下递推公式 设T(n)为算法在长度为n的数组中的运行时间
T(n) = T(n/3) + O(1)
由主定理得
T(n) = O(log n)