这个函数的运行时复杂性是什么？

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. 我的朋友说它的nlog(登录)

还请告诉我 - 内部循环在这个功能中是否相互依赖？

Answer 1

它实际上是未定义的复杂性,因为你使用q未初始化.

忽略那个小bug,显然是外环O(n).第一个内环是O(log n).第二个内部循环是O(log p),它p是log n如此,O(log log n)但它无关紧要,因为它是在第一个内部循环之后顺序执行的,因此两个内部循环的总数是O(log n)(当你添加两个复杂性时,整体复杂性是增长最快的一个) .所以你的整体复杂性是O(n log n)