具有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。
• 第一个时循环是N 1。
• i--；是N次，因为它在第一个while循环中。
• j=i-1；也是N.
• 第二个时循环是（N 1）N=N^2 N，因为它是时循环中的时循环
• if语句：？？？
• j--；是N（N）=N^2
• 返回0；是1

我对计算算法的时间复杂度非常陌生，所以我甚至不确定我认为我知道的是否完全正确。但是让我困惑的是if语句，我不知道如何计算它（如果它之后还有一个其他语句呢？）

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

Answer 1

当循环迭代时，执行if检查的次数与内部检查的次数相同。

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

你最终会感觉到你可以忽略代码的哪些部分，所以你不需要计算这个“总计”，只需要意识到有两个嵌套的循环，每个循环遍历数组-即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

通常不需要对时间复杂度进行如此准确的分析。根据Big-O了解它就足够了。然而，出于自己的好奇心，我做了一些计算。

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

• 返回1语句从不执行。内部while循环执行N（N-1）/2次（总和i-1从1到N），并发生三件事-检查while条件（并计算为true），检查if条件（并计算为false），并减小变量j。因此，操作数为3N（N-1）/2
• 外部while循环执行N次，除条件检查外，还有三条语句-i递减，分配j，内部while条件失败N次。也就是说，还有4N次操作
• 在所有循环之外，还有三条语句。初始化i，while条件失败一次，然后返回语句。再加上3个

3/2N2-3/2n4n3。

那是3/2N25/2N 3。这是你的“总数”。

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