我想计算两个算法的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屋！