算法复杂度分析

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 是某个常数，这是因为如果它在循环内找到重复的元素，它会重复生成随机数并需要一些恒定的时间，am我说得对吗？

Answer 1

随着获得工作编号的可能性降低，goto 循环的数量会增加。
对于均匀随机数生成器，其行为与数字的数量呈线性关系。它绝对不会增加你的复杂性。

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

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

Answer 2

是O(无穷大)。 O 表示法给出了上限。由于您在循环中使用了 rand()，因此无法保证您会取得进展。因此，不存在上限。

[编辑]
好吧，除了传统的、最坏情况的复杂性之外，人们还想要其他的复杂性。

假设 RNG 生成无限级数得到的最坏情况复杂度；这意味着即使第一次循环迭代也没有完成。因此，运行时间没有有限上限，O(无穷大)。

最好情况的复杂度是通过假设 RNG 生成序列数来获得的。这意味着每次迭代的成本为 O(log N) (set::find)，并且有 O(N)*O(N) 次迭代，因此上限为 O(N< support>2 log N)。

平均情况的复杂性更难。假设对于某些 k > max = k*N*N 1，RNG 将在 O(1) 时间内成功选择一个“未使用”的号码。即使选择了 N*N 个号码后，仍然有 (k-1) 个未使用的号码，因此选择未使用号码的几率 p 为 p >= (k-1)* (N*N)/k*(N*N) <=> p>=(k-1)/k。这意味着我们可以期望在 k/(k-1) 次尝试中选择一个未使用的数字，这与 N 无关，因此 O(1) 无关。 set::find 仍然主导每次迭代的成本，时间复杂度为 O(log N)。我们仍然有相同的迭代次数，因此我们得到相同的 O(N2 log N) 上限

Answer 3

goto 循环直到随机数等于给定数。
如果随机数的分布是均匀的，则“重试...直到”相对于范围的幅度是“平均线性”。
但是这种线性会增加 set::find (log(n)) 的复杂性（ste::insert 仅发生一次）

两个外部 for 基于常量（因此它们的时间不依赖于数据），因此它们只会增加时间，但不会增加复杂性。

Answer 4

“复杂性”并不是你的程序需要多少绝对时间（或空间）。它是关于当您增加程序输入数据的大小时增加时间（或空间）的量。

（顺便说一句，表示时间的 O 和表示空间的 O 可能不同。）

时间复杂度

假设 n 是矩阵中的元素数量，您必须问自己添加时会发生什么矩阵中的单个元素（即，当 n 变为 n+1 时）：

• 您需要迭代新元素，时间复杂度为 O(1)。我们在这里讨论的是一次迭代，因此双循环并不重要。
• 您还有另一个打印迭代，这也是 O(1)，假设 cout<< 是 O(1)。
• 您必须找到 O(log(n)) 的元素 - std::set 通常实现为红黑树。
• 您可能必须重试find（通过goto）多次。根据 rnd、min、max 和 int 的宽度，重试次数可能为 O(1) （即它不会随着元素数量的增加而增加）或者可能比这更糟。
• 您必须插入 O(log(n)) 的元素。

假设“最佳”rnd，您将看到一个元素的以下增加...

(O(1) + O(1)) * (O(log(n)) * O(1) + O(log(n)) = O(1) * O(log(n)) = O(log(n))

...所以对于 n 个元素，您的复杂性是：

(O(n) + O(n)) * (O(log(n)) * O(1) + O(log(n)) = O(n) * O(log(n)) = O(n * log(n))

假设 O(n) 的“坏”rnd，你正在看......

(O(n) + O(n)) * (O(log(n)) * O(n) + O(log(n)) = O(n) * O(n * log(n) ) = O(n^2 * log(n))

空间复杂度

你的矩阵是 O(n) ，而 std::set 是 O(n) 所以你总体上是 O(n) 。