分区函数的t(n)复发

Question

我正在尝试确定函数的复发，然后使用主定理解决它。该功能如下：

Partition(x, A[], lo, hi){  
   if(lo > hi)  
        return hi;  
    else{  
        q = (lo + hi) / 2;  
        if(A[q] >= x)  
            return Partition(x, A[], q+1, hi);  
       else  
            return Partition(x, A[], lo, q-1);  
}  

一个注：a是非侵扰的，
据我了解，复发应该是：
t(n(= t(n/2 1( t(n/2 -1(
因为Q是n的一半开始/- 1。我不清楚的是o(n(的工作是什么？

Answer 1

我想给定算法的复发方程是

t(n(= 1 1 1 t(n/2(

1 =>对于退出条件

1 => Q计算

1 =>对于分支条件

t(n/2(=>用于分支计算

因此，t(n(= 3 t(n/2(

应用主定理：

对于形式的复发，

T(n) = aT(n/b) + f(n)
where a >= 1 and b > 1

如果f(n(为o(n ^c (，则

1. 如果C＆lt;log _b a，然后t(n(= o(n * log _b a(
2. 如果c = log _b a，则t(n(= o(n ^c * log n(
3. 如果c> log _b a，则t(n(= o(n ^c (

我们有a = 1，b = 2，c = 0和c = log _b a(案例2([as c = 0 and log 1(任何基数(= 0]

因此，t(n(= o(n ⁰ * log n(

t(n(= o(log n(