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

Question

此代码用于查找Fibonacci序列中偶数的和。我只想知道这个程序的时间复杂性

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

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

假设极限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个Fibonacci数a根据Binet公式非线性增长，该公式可以渐近地表示为：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

Answer 2

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

Answer 3

此程序的时间复杂度将为(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

sum+=b；//添加=1

}

}

System.out.println(sum(；//输出=1

所以时间复杂度是o(n(，寻找时间复杂度的小技巧是检查代码内部的循环，所以如果一个循环的复杂度是n，如果嵌套循环的复杂程度是n^2，如果上下两个循环的复杂性是2n。谢谢