嵌套循环的大O表示法

Question

我正在努力为本准则找到时间复杂性。

for (int i = 0; i <= n - 1; i++)
  for (int j = i + 1; j <= n - 1; j++)
    for (int k = j + 1; k <= n - 1; k++)

我的尝试：我们可以用以下形式编写这个循环：

for (int i = 1; i <= n; i++)
  for (int j = 1; j <= n; j++)
    for (int k = 1; k <= n; k++)

现在这个循环的大哦是O（n ^ 5）。我纠正还是犯了一些错误？

Answer 1

您的代码的第一个变体添加了一个计数器：

int count = 0
for (int i = 0; i <= n - 1; i++)
    for (int j = i + 1; j <= n - 1; j++)
        for (int k = j + 1; k <= n - 1; k++)
            count++;

这将（i，j，k）的每个组合计数为0 <= i <j <k <n。这对应于您可以从n个元素中选择3个元素的方式的数量，而不考虑它们的顺序。这个数字有a formula：

n（n-1）（n-2）/ 3！ = n3 / 6 - n2 / 2 - n / 2

第二个变种：

int count = 0
for (int i = 0; i <= n - 1; i++)
    for (int j = 0; j <= n - 1; j++)
        for (int k = 0; k <= n - 1; k++)
            count++;

...计算您可以从n个项目中选择3的方式的数量，但是顺序很重要，并且允许在3个选项中重复。这个数字很容易导出，因为i，j，k是独立的，每个都可以得到n个不同的值，所以总数是：

我们是

现在它们代表了同样的时间复杂性：

A / n / i / n / 2 - n / a）= a（n）

这是因为properties of big O：

如果函数可以由n中的多项式界定，那么当n倾向于无穷大时，可以忽略多项式的低阶项。

和：

乘以常数 设k为常数。然后： 如果k非零，则O（kg）= O（g）。

Answer 2

现在这个循环的大哦是O（n ^ 5）。我纠正还是犯了一些错误？

不，这不正确。复杂性是qazxsw poi。

简单来说，你可以这样想：

从O(n^3)开始并到达0的每个for循环中执行的最大步骤为n-1。因此，如果您有两个循环，一个嵌套在另一个循环中，那么对于您在外循环中创建的每个步骤，您将在嵌套循环中生成n步骤。鉴于你将在外圈中做出的步骤是n，很明显，最后你将制作n步骤。

基于以上所述，您可以在以下情况下轻松绘制：

n^2

你会做

for(int i=0; i<=n-1; i++)
{
    for(int j=0; j<=n-1; j++)
    {
        for(int k=0; k<=n-1; k++)
        {

        }
    }
}

步骤。所以复杂性是n^3的顺序。

Answer 3

那些循环嵌套了吗？如果是这样，那么你就是在正确的轨道上重写这样的循环，以便更容易推理。虽然我会给每个循环一个不同的迭代器名称，以避免混淆：

O(n^3)

实际上，您可以将这些变量重命名为您想要的任何内容，以便更容易推理。怎么样：

for (int a = 1; a <= n; a++) {
    for (int b = 1; b <= n; b++) {
        for (int c = 1; c <= n; c++) {
            ...
        }
    }
}

现在，问题变成了，如果我必须访问n个城市的n个房间的n个房间，我需要访问多少个房间？

希望你能看到答案是n * n * n，即n ^ 3。

获得答案的快捷方式是看到你有3个嵌套for循环从1到n，所以答案是n ^ 3。

Answer 4

如果你有疑问，你想说服自己只是做一点测试：

for (int street = 1; street <= n; street++) {
    for (int house = 1; house <= n; house++) {
        for (int room = 1; room <= n; room++) {
            ...
        }
    }
}

结果：

#include <stdio.h>

int main()
{
int count1=0,count2=0;
int n=100;

for (int i = 0; i <= n - 1; i++)

for (int j = i + 1; j <= n - 1; j++)

for (int k = j + 1; k <= n - 1; k++)
  count1++;

for (int i = 1; i <= n; i++)

for (int j = 1; j <= n; j++)

for (int k = 1; k <= n; k++)
  count2++;

printf("count1 %d count2 %d n %d\n",count1,count2,n);
return 0;
}

• 显然，第二个循环运行count1 161700 count2 1000000 n 100 次=> O（n ** 3）
• 第一个循环由于边界而运行较少，但它仍然是线性的（在边界上没有除法运算）=> O（n ** 3），即使它更快。