语句3执行的频度为怎么解

FOR j:=n DOWNTO i DO {语句3} 这里有变量i说明这个For是在第一个For i循环里的，频度应为n的平方

但FOR i:= n DOWNTO 1 DO {语句1} 说明For i在这一行已经结束了，原程序不是这样写的吧？

算法的复杂性

算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。

计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。

不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。

简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。

1时间复杂性：

例1：设一程序段如下（为讨论方便，每行前加一行号）

(1) for i:=1 to n do

(2) for j:=1 to n do

(3) x:=x+1

试问在程序运行中各步执行的次数各为多少？

解答：

行号 次数(频度)

(1) n+1

(2) n(n+1)

(3) nn

可见，这段程序总的执行次数是：f(n)=2n2+2n+1。在这里，n可以表示问题的规模，当n趋向无穷大时，如果 f(n)的值很小，则算法优。作为初学者，我们可以用f(n)的数量级O来粗略地判断算法的时间复杂性，如上例中的时间复杂性可粗略地表示为T(n)=O(n2)。

2空间复杂性:

例2:将一一维数组的数据(n个)逆序存放到原数组中,下面是实现该问题的两种算法:

算法1:for i:=1 to n do

b[i]:=a[n-i+1];

for i:=1 to n do

a[i]:=b[i];

算法2:for i:=1 to n div 2 do

begin

t:=a[i];a[i]:=a[n-i-1];a[n-i-1]:=t

end;

算法1的时间复杂度为2n,空间复杂度为2n

算法2的时间复杂度为3n/2,空间复杂度为n+1

显然算法2比算法1优，7a64e78988e69d8331333262383561这两种算法的空间复杂度可粗略地表示为S(n)=O(n)

信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。

分析每一次循环可以发现，当循环执行10次后x>100，y方才减1，此时x被复原为91；

如此下去，由于每执行10次循环才使y减1，所以循环体执行10010次，也就是说if语句判断执行了1000次（但里面的y--执行了100次）。至于时间复杂度，你现在数据都给定值了那不就是o(1)吗……如果x、y没给初值，则粗略地说应该为o(y)（或者说是o(10y)）。

以上就是关于语句3执行的频度为怎么解全部的内容，包括:语句3执行的频度为怎么解、程序中选择执行的两段代码复杂度不同程序复杂度怎么取、分析下面算法（程序段）给出最大语句频度 ，该算法的时间复杂度是__ __。等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！