这个JAVA程序的时间复杂度是多少

Question

这段代码是用来求斐波那契序列中偶数的和。我只是想知道这个项目的时间复杂性

int sum = 2;
int a = 1;
int b = 2;

while (a < 4000000) {
 int c = a;
 a = b;
 b = c + b;
 if (b % 2 == 0) {
  sum += b;
 }
}

System.out.println(sum);

如果我也能得到一个解释，我将不胜感激

Answer 1

这很简单。迭代集合中的所有元素——这是O(n)或linear complexity

Answer 2

这个程序的时间复杂度将是（n+5）+3+1=n+9=o（n），以下是计算

`int sum=2；//常数=1

int a=1//常数=1

int b=2//常数=1

而（a<；4000000）{//loop=n

int c=a//常数=1

a=b//赋值=1

b=c+b//赋值=1

如果（b%2==0）{//如果条件=1

总和+=b；//加法=1

}

}

系统。出来println（总和）；//输出=1

所以时间复杂度是o（n），找到时间复杂度的短技巧是检查代码内部的循环，如果一个循环的复杂度是n，如果嵌套循环的复杂度是n^2，如果上下两个循环的复杂度是2n，其他所有循环的复杂度是相同的。谢谢

Answer 3

首先，这个特定的代码段具有恒定的时间复杂度，因为它没有任何定义执行时间的变量

假设limit 4000000定义了这样的变量参数，从而限制了最大斐波那契数Fk < N：

    public static int sumEvenFibos(int n) {
        int sum = 2;
        int a = 1;
        int b = 2;
        int k = 1; // index of Fibonacci number
        while (a < n) {
         int c = a;
         a = b;
         b = c + b;
         if (b % 2 == 0) {
          sum += b;
         }
         k++;
        }
        
        System.out.println("sum=" + sum + "; k=" + k + " for n=" + n);
        return sum;
    }

那么这个函数的时间复杂度比O（N）低，因为第k个斐波那契数a根据Binet's formula非线性增长，可以渐近地表示为：Fk ~= φ^K / sqrt(5)，其中φ = (1 + sqrt(5))/2 > 1是黄金比率

因此，在循环中最多计算k个斐波那契数，即：

Fk < N,   φ^K / sqrt(5) < N   > φ^K < N * sqrt(5)

hence,
          K < log(N * sqrt(5)) / log (φ)

由于在定义时间复杂度时可以忽略常量值，T(N) = O (log N)

偶数斐波那契数的sum运算数为K/3，因为每三个斐波那契数都是偶数： 1.123.5811.1324等

测试与维护；产出

    int[] ns = {
        10, 100, 1000, 10_000, 100_000, 
        1000_000, 2000_000, 4000_000, 
        10_000_000, 20_000_000, 40_000_000, 
        80_000_000, 160_000_000
    };
    Arrays.stream(ns).forEach(MyClass::sumEvenFibos);
    -
sum=10; k=6 for n=10
sum=188; k=11 for n=100
sum=3382; k=16 for n=1000
sum=14328; k=20 for n=10000
sum=257114; k=25 for n=100000
sum=1089154; k=30 for n=1000000
sum=4613732; k=31 for n=2000000
sum=4613732; k=33 for n=4000000
sum=19544084; k=35 for n=10000000
sum=19544084; k=36 for n=20000000
sum=82790070; k=38 for n=40000000
sum=82790070; k=39 for n=80000000
sum=350704366; k=40 for n=160000000