c++ - 算法复杂度分析

Question

这是代码，它用 [1 19] 范围内的随机生成数字填充二维数组，没有重复，我的问题是:如何确定它的复杂性？

例如，我看到它的运行时间至少是 O(n^2)，因为它有内部和外部循环，但是关于 goto 语句呢？

这是我的代码:

#include <iostream>
#include <set>
#include <cstdlib>
using namespace std;

int main()
{
    int min=1;
    int max=19;
    int  a[3][3];
    set<int>b;

    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
        {
loop:
            int m=min+rand()%(max-min);

            if (b.find(m)==b.end())
            {
                a[i][j]=m;
                b.insert(m);
            }
            else
                goto loop;
        }
    }

    for (int i=0; i<3; i++)
    {
        for (int j=0; j<3; j++)
            cout<< a[i][j]<<"  ";
        cout<<endl;
    }
    return 0;
}

我会说算法的复杂度是 c*O(n^2)，其中 c 是某个常数，这是因为如果它在循环中找到重复的元素，它会重复生成随机数并花费一些常数时间，我说得对吗？

Answer 1

随着获得有效数字的可能性降低，goto 循环的数量会增加。对于统一的随机数生成器，行为相对于数字的数量是线性的。它绝对不会增加您的复杂性。

如果 n 是 a 中元素的数量，那么它的平均规模为 O(n²)。 (或者如果 n 是方阵 a 中的行数；O(n⁴))。

一个更简单的实现是使用 Fisher-Yates shuffle