找到嵌套循环的计算复杂性

Question

我很难获得这个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和复杂性的文章,但它们没有用,因为他们希望我知道一切,他们的例子和我的任何例子都不一样.

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

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

Answer 1

您可以看到外循环迭代(n-4)次,因为它从4开始并且条件小于仅.内循环最多迭代4次.因为它以i-3开头并以i结束.所以复杂度是4*(n-4).因此,复杂性是O(n).