英文:
What is the Time Complexity of this JAVA program
问题
这段代码是用来计算斐波那契数列中偶数数字的和。我只想知道这个程序的时间复杂度。
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);
如果您需要解释，请告诉我。
英文:
This code is to find sum of even numbers in Fibonacci sequence. I just wants to know the Time complexity of this program
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);
I would be thankful if I get an explanation too.
答案1
得分: 3
这个特定的代码片段具有常数时间复杂度，因为它没有定义任何定义执行时间的变量。
假设限制4000000定义了这样一个变量参数，从而限制了最大的斐波那契数Fk < N：
public static int sumEvenFibos(int n) {
int sum = 2;
int a = 1;
int b = 2;
int k = 1; // Fibonacci数的索引
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的公式非线性增长，可以渐近地表示为：Fk ~= φ^K / sqrt(5)，其中φ = (1 + sqrt(5))/2 > 1是黄金比例。
因此，在循环中最多计算了k个斐波那契数，即：
Fk < N, φ^K / sqrt(5) < N --> φ^K < N * sqrt(5)
所以，
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
英文:
First, this specific code snippet has constant time complexity as it does not have any variable defining the time of execution.
Let's assume that the limit 4000000 defines such variable parameter thus limiting maximum Fibonacci number 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;
}
Then this function has lower time complexity than O(N) because the k-th Fibonacci number a grows non-linearly according to Binet's formula which can be expressed asymptotically as: Fk ~= φ^K / sqrt(5), where φ = (1 + sqrt(5))/2 > 1 is golden ratio.
Thus, in the the loop at most k Fibonacci numbers are calculated, that is:
Fk < N, φ^K / sqrt(5) < N --> φ^K < N * sqrt(5)
hence,
K < log(N * sqrt(5)) / log (φ)
As the constant values can be ignored when defining time complexity, T(N) = O (log N).
The number of sum operations for even Fibonacci numbers is K/3 because each third Fibonacci number is even:
1 1 2 3 5 8 11 13 24 etc.
Test & Output
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
答案2
得分: 1
这很简单。您在集合中迭代所有元素 - 这是O(n)或线性复杂度。
英文:
This is simple. You iterate over all elements in the collection - this is O(n) or linear complexity
答案3
得分: -1
这个程序的时间复杂度将是 (n+5)+3+1 = n+9 = o(n)，以下是计算过程...
int sum = 2; // 常数 = 1
int a = 1; // 常数 = 1
int b = 2; // 常数 = 1
while (a < 4000000) { // 循环 = n
int c = a; // 常数 = 1
a = b; // 赋值操作 = 1
b = c + b; // 赋值操作 = 1
if (b % 2 == 0) { // 条件判断 = 1
sum += b; // 加法操作 = 1
}
}
System.out.println(sum); // 输出 = 1
所以时间复杂度为 o(n)，一个简便的计算时间复杂度的方法是检查代码中的循环数量，如果有一个循环，复杂度为 n，如果有嵌套循环，复杂度为 n^2，如果上下有两个循环，复杂度为 2n，其他情况类似。谢谢。
<details>
<summary>英文:</summary>
The Time complexity of this program will be (n+5)+3+1 = n+9 = o(n) and below is the calculation....
`int sum = 2; // constant =1
int a = 1; //constant = 1
int b = 2; //constant = 1
while (a < 4000000) { //loop = n
int c = a; //constant = 1
a = b; //assigning value = 1
b = c + b; //assigning value = 1
if (b % 2 == 0) { //if condition = 1
sum += b; // addition = 1
}
}
System.out.println(sum); // output = 1
so the time complexity will be o(n) and short trick of finding time complexity is check loops inside code so if one loop so complexity is n and if nested loop complexity is n^2 and if two loop up and below so complexity is 2n and same for all other. Thanks.
</details>
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论