c - 这个函数的运行时间复杂度是多少？

Question

void fn(int n){

    int p,q;
    for(int i=0;i<n;i++){
        p=0;
        for(int j=n;j>1;j=j/2)
            ++p;
        for(int k=1;k<p;k=k*2)
            ++q;

    }

}

1. 我认为它的复杂度是nlogn
2. 我的 friend 说它是 nlog(logn)

还请告诉我 - 这个函数中的内部循环是否相互依赖？

Answer 1

它实际上具有未定义的复杂性，因为您使用的是未初始化的 q。

忽略那个小错误，外循环显然是O(n)。第一个内部循环的时间复杂度为O(log n)。第二个内部循环是 O(log p) 且 p 是 log n 所以它是 O(log log n) 但这并不重要，因为它是在第一个内部循环之后顺序执行的，因此两个内部循环的总复杂度是 O(log n) (当您添加两个复杂度时，总体复杂度是增长最快的一个)。所以你的整体复杂度是O(n log n)