在一个具体的程序中，程序的复杂度是如何计算的？

算法的复杂性

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

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

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

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

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) n*n

可见，这段程序总的执行次数是：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的时间复杂度为3*n/2,空间复杂度为n+1

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

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

因为它采用的思想是“面向对象”，其特点之一是使用直观的，直接面向图形对象的方法设计应用程序，即设计用户界面时可以不编写代码，其结果是使程序设计变得相对简单和容易。因此能够有效提高编程的效率和降低编程难度和复杂度。

程序执行的效率跟算法有关，而一个算法的优劣可以用空间复杂度与时间复杂度来衡量。

1、空间复杂度是指算法在计算机内执行时所需存储空间的度量

2、一般情况下，算法中基本 *** 作重复执行的次数是问题规模n的某个函数，用T(n)表示，若有某个辅助函数f(n),使得当n趋近于无穷大时，T（n)/f(n)的极限值为不等于零的常数，则称f(n)是T(n)的同数量级函数。记作T(n)=O(f(n)),称O(f(n)) 为算法的渐进时间复杂度，简称时间复杂度。

在各种不同算法中，若算法中语句执行次数为一个常数，则时间复杂度为O(1),另外，在时间频度不相同时，时间复杂度有可能相同，如T(n)=n2+3n+4与T(n)=4n2+2n+1它们的频度不同，但时间复杂度相同，都为O(n2)。

按数量级递增排列，常见的时间复杂度有：

常数阶O(1),对数阶O(log2n),线性阶O(n),线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，

k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

---