时间戳

首页 > 解决方案 > 这个 JAVA 程序的时间复杂度是多少

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

问题描述

此代码用于查找斐波那契数列中偶数的总和。我只想知道这个程序的时间复杂度

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);

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

标签： javatime-complexity

解决方案

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

让我们假设限制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 个斐波那契数根据Binet 公式a非线性增长，该公式可以渐近表示为：，其中是黄金比例。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 1 2 3 5 8 11 13 24等。

测试与输出

    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

推荐阅读