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-D大小的任何N数组，我是说复杂度将为N!。这是正确的吗？

下面两种算法的复杂度是什么（大小是每个维的长度）？： void a（int ** arr，int size）{int k = 0; for（int i = 0; i

时间复杂度：

• 第一个函数的时间复杂度是-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)。

我相信第一个函数是O（N ^ 2），第二个函数是O（N ^ 3）。这是正确的吗？

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

对于任何N大小的N-D数组，我要说的复杂度将是N!。这是正确的吗？

不完全是。复杂度将为N ^ N（从N到N的幂），更高]

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

N！ = N *（N-1）* ... * 1

（（要找到两者之间的比例，可以顺便使用Stirling's approximation。]

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

我认为您跳过了分析中的重要一步。您首先查看两个示例案例（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表示在公式中将D替换为N是有效的；复杂度为O(N^N)。

Answer 1

时间复杂度：

Answer 2

我相信第一个函数是O（N ^ 2），第二个函数是O（N ^ 3）。这是正确的吗？

Answer 3

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