具有嵌套 if 语句和 for 循环的算法的时间复杂度

Question

所以我正在尝试解决这个问题，但我和我的朋友对此有点困惑

for (Int64 i = 1; i < Math.Pow(2, n); i = 2*i)
{
    if (i <= 4 || i >= Math.Pow(2, n - 2))
    {
        for (Int64 j = n; j >= 0; j = j - 2)
        {
            //constant number of C operations
        }
    }
    else
    {     
        for (Int64 j = n; j > 1; j = (Int64) Math.Ceiling((double) j/2))
        {
            //constant number of C operations
        }
    }
}

我知道外层循环是 O(n) 但我不知道内部是什么，我很确定它只是 O(n) 因为最大的内部 for 循环在顶部一个在 O(n) 与下一个 O(log n) 相对应。
这是正确的思考方式吗？还是我错了

Answer 1

but I can't get what the inner part is, I'm pretty sure it's just O(n) since the largest of the inner for loops i the top one at O(n) as apposed to the lower one which is O(log n)

最上面的内循环确实是Θ(n)。这并不意味着内部是 Θ(n)，至少在你应该将其乘以 Θ(n)[=25= 的意义上不是这样]的外循环，得到整体Θ(n²)。这是因为内部的顶部循环只执行了固定次数。顶部内循环的 Θ(n) 应该 added 到外循环的。

这段代码的整体复杂度是Θ(n log(n))。具体来说就是 Θ(n) Θ(log(n))（底层内循环一共执行的总复杂度）+ Θ(n) + Θ(n )（执行顶层内循环的总复杂度）。

具有嵌套 if 语句和 for 循环的算法的时间复杂度

Time Complexity of algorithm with nested if statement and for loops

theory

algorithm

big-o