带有 while 循环和 if 语句的函数的时间复杂度

Question

int dup_chk(int a[], int length) 
{
  int i = length;
  while (i > 0)
  {
    i--;
    int j = i -1;
    while (j >= 0)
    {
      if (a[i] == a[j])
      {
        return 1;
      }
      j--;
    }
  }
  return 0;
}

所以我认为我知道的是：

第 1 行只有 1。
第一个 while 循环是 N+1。
我--;自从它在第一个 while 循环中以来是 N 次。
j = i -1;也是N.
第二个 while 循环是 (N+1)N = N^2+N 因为它是 while 循环中的 while 循环
if语句：???
j--;是 N(N) = N^2
return 0;是 1

我对计算算法的时间复杂度真的很陌生，所以我什至不确定我认为我知道的是否完全正确。但是困扰我的是 if 语句，我不知道如何计算它（如果它后面还有一个 else 怎么办？）

编辑：总计等于 3/2N^2 + 5/2N+3 我知道这个函数是 O(N^2) 但不太明白总计是如何计算的。

Answer 1

if 检查的执行次数与内部 while 循环迭代的次数一样多。

根据定义，return 1 最多只执行一次。您似乎假设输入中没有重复项（即最坏的情况），在这种情况下 return 1 语句永远不会执行。

您最终会了解可以忽略代码的哪些部分，因此您不需要计算这个 "grand total"，只需意识到有两个嵌套循环分别遍历数组- IE。 O(N^2).

Answer 2

也许这可以帮助您了解代码中出了什么问题。我添加了一些打印输出，使您更容易理解代码中发生的事情。我认为这应该足以找到你的错误

int dup_chk(int a[], int length)
{
    int j = 0;
    int i = length;
    char stringa[30];

    printf("Before first while loop j = %d and i = %d \n", j, i);
    while (i > 0)
    {
        i--;
    j = i - 1;
    printf("\tIn first while loop j = %d and i = %d\n", j, i);
    while (j >= 0)
    {
        printf("\t\tIn second while loop j = %d and i = %d\n", j, i);
        if (a[i] == a[j])
        {
            printf("\t\tIn if statment j = %d and i = %d\n", j, i);
            return 1;
        }
        j--;
        printf("\t\tEnd of second while loop j = %d and i = %d\n", j, i);
    }
}
printf("After first while loop j = %d and i = %d \n", j, i);
printf("Press any key to finish the program and close the window\n");
return 0;
}

我还应该建议调试您的代码以了解更好的情况。

Answer 3

int dup_chk(int a[], int length) 
{
  int i = length;
  while (i > 0)  // Outer loop
  {
    i--;
    int j = i -1;
    while (j >= 0)  // Inner loop
    {
      if (a[i] == a[j])
      {
        return 1;
      }
      j--;
    }
  }
  return 0;
}

上面的程序正是你的代码，我冒昧添加了两条注释。

让我们考虑最坏的情况（因为这是每个人都关心/担心的）。如果仔细观察，您会发现对于 i 的每个值，Inner loop 执行 i - 1 次。因此，如果您的 Outer loop 执行 n 次，则 Inner loop 将总共执行 n * (n - 1) 次（即 n 的每个值执行 n - 1 次） .

n * (n - 1) 在一般代数中产生 n^2 - n。现在，随着您继续增加 n 的值，n^2 会突飞猛进地增加（与 n 相比）。渐近符号让我们考虑对要执行的步骤数影响最大的因素。因此，我们可以忽略 n 并说该程序的最坏情况运行时间为 O(n^2)。

这就是 Big-O 表示法的优美和简单。 - 从上面的评论中引用 Jonathan Leffler。

Answer 4

通常不需要这么准确的时间复杂度分析。从 Big-O 的角度了解它就足够了。不过出于好奇，我算了一下。

如果您只关心最坏情况分析以获得时间复杂度，请考虑仅包含唯一元素的数组。在这种情况下：

return 1 语句永远不会执行。内部 while 循环执行 N(N-1)/2 次（从 1 到 N 求和 i-1），然后发生三件事 - while 条件被检查（并计算为真），if 条件被检查（并评估为 false）并且变量 j 递减。因此，操作次数为3N(N-1)/2。
外层while循环执行了N次，除了条件检查外还有3条语句——i递减，j赋值，内层while条件失败N次。也就是多了 4N 次操作。
在所有循环之外，还有三个语句。 i的初始化，while条件失败一次，然后是return语句。再加 3 个。

3/2N² - 3/2N + 4N + 3.

那是3/2N² + 5/2N + 3。还有你的'grand total'.

再说一遍，这个计算对于所有实际目的来说都是完全没有必要的。

Answer 5

全面评价：

这个程序有一个特点：如果找到一对 (a[I], a[J]) 个相等的值，它就会终止。假设我们知道 I 和 J（我们稍后会看到如果没有这样的一对怎么办）。

外循环执行了所有 I <= i < L 次，因此执行了 L-I 次。每次，内循环执行所有 0 <= j < i，因此 i 次，除了最后一次（i = I）：我们有 J <= j < I 因此 I-J迭代。

我们假设循环的 "cost" 的形式是 a N + b，其中 a 是单次迭代的成本，b 是一些恒定的开销。

现在内层循环，运行L-I次，迭代次数递减，使用"triangular numbers"公式，成本为

a (L-1 + L-2 + ... I+1 + I-J) + b (L - I) = a ((L-1)L/2 - I(I+1)/2 + I-J) + b (L-I)

我们加上外层循环的代价得到

a ((L-1)L/2 - I(I+1)/2 + I-J) + b (L-I) + c

（其中 b 是与上面不同的常量）。

一般来说，这个函数在L中是二次的，但是如果很快找到一对（比如I = L-3），它就变成线性的；在最好的情况下 (I = L-1,J = L-2)，它甚至是常量 a + b + c.

最坏的情况发生在最后找到对 (I = 1, J = 0) 时，这实际上等同于没有找到对。那么我们有

a (L-1)L/2 + b (L - 1) + c

显然 O(L²).

带有 while 循环和 if 语句的函数的时间复杂度

Time complexity of a function with while loops and an if statement

c

algorithm

time-complexity

big-o

analysis