我想计算两个算法的T(n) [英] i want to calculate the T(n) for the two algorithms
问题描述
我想知道以下两种算法的时间复杂度
void main(){------ ----------------------------------- T(n)
for(int a = 1; a <= 20; a ++){------------?
if(a%2 == 0)-------------?
cout<<value is Even; --------?
else
cout<<value is Odd; --------?
}
}
void main(){------------------------------------ ----- T(n)
int x = 1; {------------?
int a = 1; -------------?
while(a <= n){--------?
x = x * a; -------------?
a = a + 2; -------------?
}
cout<< x;
}
一段代码的执行时间 - 通常是一些算法,取决于输入。如果函数接受N作为输入,如果N = 5或N = 10,则执行需要多长时间。它会采取双倍的时间吗?会采取同一时间吗?
第一个程序不依赖于任何输入,所以它是O(n)= 1。
您的第二个程序取决于n。它将做同样的东西n / 2次,由于a = a + 2。所以它是O(n)= n / 2。但是常数通常被跳过,一个人会写O(n)= n。
如果你有这样的代码:
for(a = 0; a {
// n times here
for(b = 0; b< ; n; b ++)
{
// n次这里
//做某事
}
}
执行时间将更改为n ^ 2,因为两个循环将迭代n次。每次外循环执行时,内循环执行n次。由于外循环执行了n次,你有n * n。所以O(n)= n ^ 2
i want to know the time complexity for the following two algorithms
void main (){-----------------------------------------T(n)
for(int a=1 ; a<=20 ; a++) {------------?
if(a%2==0) -------------?
cout<<"value is Even"; --------?
else
cout<<"value is Odd";--------?
}
}
void main (){-----------------------------------------T(n)
int x=1; {------------?
int a=1; -------------?
while(a<=n){--------?
x=x*a; -------------?
a=a+2; -------------?
}
cout<<x;
}
The idea is to calculate how the execution time for a piece of code - typically some algorithm, depends on the input. If a function takes N as input how long will it take to execute if N=5 or N=10. Will it take double as long? Will it take the same time? Or will it take more than double?
In your case:
The first program doesn't depend on any input so it is O(n)=1.
Your second program depends on n. It will do the same stuff n/2 times due to the a = a + 2. So it is O(n)=n/2. However constants are typically skipped and one would write O(n) = n.
If you had code like this:
for (a=0; a < n; a++)
{
// n times here
for (b=0; b<n; b++)
{
// n times here
// do something
}
}
the execution time will change to n^2 because both loops will iterate n times. Each time the outer loop executes, the inner loop executes n times. Since the outer loop executes n times, you have n*n. So O(n) = n^2
这篇关于我想计算两个算法的T(n)的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!