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

两个循环上的索引变量是独立的，因此产生的复杂度必然相同。

于 2012-04-27T16:58:44.227 回答
0

您仍在循环相同数量的迭代。更改循环的顺序不会影响复杂性

于 2012-04-27T17:01:04.710 回答