amortized-analysis - ループの時間計算量分析:

Question

時間計算量が O(nlogn) ではなく O(n) なのはなぜですか? 外側のループの複雑さと内側のループの複雑さを掛け合わせる必要はありませんか?

    int fun(int n){
    int count = 0;
    for (int i = n; i > 0; i /= 2)
        for (int j = 0; j < i; j++)
            count += 1;
    return count;
    }

Answer 1

ループの最初の反復では、内側のループが n の半分をカバーします。次の反復では、4 分の 1、8 分の 1、というように続きます。以下の関数で係数を表すことができます。ご覧のとおり、合計すると 1 になる無限級数です。したがって、関数全体は O(n)