0

それで、私は Big Oh の計算を理解しようとしてきました。基本的なことはできたと思いますが、本当に簡単に見える計算に困惑しています。したがって、以下の計算が O(n log n) の大きな問題を抱えている場合 (少なくともそれが正しいことを願っています)、ループの順序を変更すると複雑さが増しますか? お時間をいただきありがとうございます。

    int ONLogN(int N) //O(n log n)
    {
        int iIterations = 0;
        for (int i = 0; i < N; ++i)
        {
            ++iIterations;
            for (int j = 1; j < N + 1; j *= 2)
                ++iIterations;
        }
        return iIterations;
    }
    int WhatBigOhIsThis(int N) //???
    {
        int iIterations = 0;
        for (int j = 1; j < N + 1; j *= 2)
        {
            ++iIterations;
            for (int i = 0; i < N; ++i)                
                ++iIterations;
        }
        return iIterations;
    }
4

2 に答える 2

1

2 つのループのインデックス変数は独立しているため、結果の複雑度は必然的に同じになります。

于 2012-04-27T16:58:44.227 に答える
0

同じ回数の反復でループし続けています。ループの順序を変更しても、複雑さに影響はありません

于 2012-04-27T17:01:04.710 に答える