首页 > 试题广场 >

给定一递归算法的程序段如下(r -l1),设n=r-l+1

[单选题]

给定一递归算法的程序段如下(r -l>1),设n=r-l+1,则该算法的时间复杂度为()。

void f(int l, int r)
{
    for(int i = l; i <= r; i ++ ) a[i] ++ ;
    if(l == r) return ;
    int mid = (l + r) / 2;
    f(l, mid);
    f(mid + 1, r);
    return ;
}
int main()
{
    n = r - l + 1;
    f(l, r);
}
根据master,T(N)=2T(N/2)+N,即a=b=2,d=1,所以复杂度为O(nlogn)

发表于 2022-09-21 11:31:42 回复(0)
T(N)=2T(N)+O(N),由master定理可得,时间复杂度O(N*log(N))。
发表于 2021-12-19 11:25:11 回复(0)