具有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循环
• 如果声明:???
• j--; 是N(N)= N ^ 2
• 返回0; 是1

我真的很想计算算法的时间复杂度,所以我甚至不确定我认为我所知道的是完全正确的.但是弄乱我的是if语句,我不知道如何计算(以及如果之后还有其他内容呢？)

编辑:总计等于3/2N ^ 2 + 5/2N + 3我明白,这个函数是O(N ^ 2),但不完全得到总计是如何计算的.

Answer 1

通常不需要对时间复杂度进行如此准确的分析.用Big-O来了解它就足够了.但是,我为自己的好奇做了一些计算.

如果您的关注只是获得时间复杂度的最坏情况分析,请考虑仅包含唯一元素的数组.在这种情况下:

• 该return 1语句根本不会执行.内部while循环执行N(N-1)/ 2次(求和i-1从1到N),并发生三件事 - while检查条件(并计算为真),if检查条件(并计算为false) )并且变量j递减.因此,操作次数为3N(N-1)/ 2.
• 外while循环执行N次,除条件检查外还有三个语句 - i递减,j分配,内部while条件失败N次.那是4N以上的操作.
• 在所有循环之外,还有三个语句.初始化i,while条件失败一次,然后返回语句.再添加3个我们的计数器.

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

这是3/2N ² + 5/2N + 3.有你的'总计'.

重复一遍,这个计算对于所有实际目的来说完全没有必要.