c - 这个双重嵌套循环的时间复杂度是多少？

Question

您好，我对以下代码片段的时间复杂度有点困惑， 如果有人能够阐明这一点，那就太好了。

     for ( i = 1; i <= n ; i ++)
        for ( j= i+1; j <= n; j++)
          //print something

Answer 1

在这种情况下，请记住这一点:

When in doubt, work inside out!

让我们获取您的代码:

 for ( i = 1; i <= n ; i ++)
    for ( j= i+1; j <= n; j++)
      //print something

在这里，打印某些内容的成本是 θ(1)(假设您总是打印相同的内容)，因此我们可以像这样重写此代码:

 for ( i = 1; i <= n ; i ++)
    for ( j= i+1; j <= n; j++)
       do Θ(1) work

现在，让我们从内到外进行工作。那个内循环要做什么？好吧，当 i = 1 时，它将运行 n - 1 次迭代。当 i = 2 时，它将运行 n - 2 次迭代。当 i = 3 时，它将运行 n - 3 次迭代。从这个意义上说，完成的工作是 θ(n - i)，所以我们可以用这样的东西替换内部循环:

 for ( i = 1; i <= n ; i ++)
    do Θ(n - i) work

现在，让我们看看这个外循环。第一次，这将执行(大约) n - 1 项工作，第二次将执行 n - 2 项工作，第三次将执行 n - 3 项工作，依此类推。换句话说，总共这里完成的工作(大致)等于

(n - 1) + (n - 2) + (n - 3) + ... + 3 + 2 + 1

这是一个著名的数字，叫做 Gauss's sum ，其值为 n(n - 1)/2，即 θ(n²)。因此，正如@Lashane 在他们的评论中指出的那样，这里完成的总工作是 θ(n²)。