3

我很难理解这个 for 循环的复杂性

for (i = 4; i < n; i++)
{
    for (j = i - 3, sum = a[i - 4]; j <= i; j++)
    {
        sum += a[j];
    }
    System.out.println("sum thru" + i + ": " + sum);
}

我在想这个嵌套循环的复杂度是 n^2，因为它是一个嵌套循环，但有人告诉我这是不正确的，嵌套循环并不总是二次复杂度！

我真的不知道如何以一种好的方式获得复杂性。我看过很多关于 Big-O 和复杂性的文章，但它们并没有帮助，因为他们希望我了解所有内容，而且它们的示例与我拥有的任何示例都不相同。

我不是要答案，我要的是方法。是否有任何公式或方法适用于本主题中的所有内容？我想知道如何获得分配的数量，但不幸的是我不知道如何做到这一点。

有人可以逐步向我解释吗？

4

2 回答 2

10

您可以看到外部循环迭代 (n-4) 次，因为它从 4 开始并且条件小于 only。内部循环将最多迭代 4 次。因为它以 i-3 开头，以 i 结尾。所以复杂度是 4*(n-4)。因此复杂度为 O(n)。

于 2013-09-20T01:35:46.920 回答
0

我认为没有任何公式可以解决有关算法时间复杂度的所有问题。对我来说，找出大 O 的最好方法是一步一步地，从外部过程到内部过程。我相信这也是像你我这样的初学者的标准方式。对于您的问题，首先，外循环是 O(n)，这是直截了当的。然后在每个循环内部，我们有一个内部过程，这是另一个循环。该循环从 i-3 到 i，即 O(1)。然后在那个过程中，它是一个正常的赋值语句，又是 ​​O(1)。我们综合考虑，大 O 将是 O(n) * O(1) * O(1) = O(n)

于 2013-09-20T01:44:23.443 回答