N维数组的大O符号

Question

下面两种算法的复杂度是多少（size是每个维度的长度）？：

void a(int** arr, int size) {
    int k = 0;

    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            arr[i][j] += 1;
        }
    }
    print(arr, size);
}

void b(int*** arr, int size) {
    int m = 0;

    for (int i = 0; i < size; ++i)
    {
        for (int j = 0; j < size; ++j)
        {
            for (int k = 0; k < size; ++k)
            {
               arr[i][j][k] += 1;
            }
        }
    }
    print(arr, size);
}

我认为第一个函数是 O(N^2)，第二个函数是 O(N^3)。这是正确的吗？对于任何 N 大小的 N-D 数组，我的意思是复杂度将是 N!。这是正确的吗？

Answer 1

I believe the first function is O(N^2) and the second function is O(N^3). Is this right?

是的，第一个是N * N，第二个是N * N * N

For any N-D array of N size I am saying the complexity will be N!. Is this correct?

不完全是。复杂度会是N^N（N的N次方），更高

N^N = N * N * .... * N

N！ = N * (N - 1) * ... * 1

（求两者的比值，可以用Stirling's approximation，顺带一提。）

Answer 2

时间复杂度：

第一个函数的时间复杂度是 - O(size^2)
第二个函数的时间复杂度是 - O(size^3)
对于类似函数，每个大小为 N 的 N 维数组的时间复杂度为 - O(N^N)，因为所需的迭代次数为 N * N * N... 最多 N 次.

因此，您在前两个方面是正确的 - O(N^2) 和 O(N^3) 如果 N 您的意思是 size。然而，最后的说法是不正确的。 N! 比 N^N 增长得慢，因此 N! 作为上限是错误的。应该是 O(N^N).

Answer 3

I believe the first function is O(N^2) and the second function is O(N^3). Is this right? For any N-D array of N size I am saying the complexity will be N!. Is this correct?

我认为您在分析中跳过了一个重要步骤。您首先查看了两个示例案例（2-D 和 3-D）。到目前为止，一切都很好。您分析了这两种情况的复杂性，确定 2-D 情况是 O(N^2)，3-D 情况是 O(N^3)。也很好。但是你跳过了一步。

下一步应该是泛化到任意维度 D。您查看了两个示例案例，您看到公式中出现了 2 和 3，因此从理论上可以合理地将其替换为 D。理论是，对于维度为 D 的数组，复杂度为 O(N^D)。理想情况下，您需要做更多的工作来证明这一点，或者至少检查它是否适用于您尚未看过的情况，例如 4-D。一旦您对这个结果有信心，您就可以继续前进了。

只有在得到任意维度情况的公式后，你才应该专攻维度等于大小的情况。这个结果相当简单，因为假设 D == N 意味着在公式中用 N 替换 D 是有效的；复杂度是 O(N^N).

N维数组的大O符号

Big O-Notation of N-Dimensional array

c++

big-o

时间复杂度：