c++ - 这个for循环的运行时间复杂度是多少

Question

for (int p = t; p > 0; p >>= 1) {
    for (int i = 0; i < n - p; ++i) {
        if ((i & p) != 0) {
            sort2(a, i, i+p);
        }
    }
    for(int q = t; q > p; q >>= 1) {
        for(int i = 0; i < n- q; ++i) {
            if ((i & p) != 0) {
                sort2(a, i+p, i+q);
            }
        }
    }
}

这里n是一些正整数，t大于n/2，但不等于n.

据我了解，内部 for 循环运行了 (n-p) 次，但我无法弄清楚外部 for 循环。

我试过如下找到它:

如果t=64和n=100，它取p的二进制值等于64 等等 p=1000000 base 2.

我理解是每次减一位，本例共执行7次。我不知何故无法弄清楚一般时间。

此外，我的理解是第三个 for 循环即

for(int q = t; q > p; q >>= 1)

根本不执行，因为条件 q>p 不满足 p=q=t。

这是正确的吗？我刚刚开始学习算法。

Answer 1

为此:复杂度将是 BigO( log(t)(n-t)log(t) )

在 for 循环中排除了 sort2 函数的复杂性。

解释:

• 外层循环复杂度为 log(p)+1 [每次右移 1 位并大于 0]，所以对于 t = 64，循环将按 [64, 32, 16, 8, 4, 2, 1] 进行。
• 内部循环复杂度将大于 ( O(n-p), O((n-t)log(t)) )

执行

对于第二个内层循环嵌套了最外层循环的for循环: