1楼：匿名用户
算法的复杂性
算法的复杂性是算法效率的度量，是评价算法优劣的重要依据。一个算法的复杂性的高低体现在运行该算法所需要的计算机资源的多少上面，所需的资源越多，我们就说该算法的复杂性越高；反之，所需的资源越低，则该算法的复杂性越低。
计算机的资源，最重要的是时间和空间（即存储器）资源。因而，算法的复杂性有时间复杂性和空间复杂性之分。
不言而喻，对于任意给定的问题，设计出复杂性尽可能低的算法是我们在设计算法时追求的一个重要目标；另一方面，当给定的问题已有多种算法时，选择其中复杂性最低者，是我们在选用算法适应遵循的一个重要准则。因此，算法的复杂性分析对算法的设计或选用有着重要的指导意义和实用价值。
简言之，在算法学习过程中，我们必须首先学会对算法的分析，以确定或判断算法的优劣。
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)
信息学比赛中，经常是：只要不超过内存，尽可能用空间换时间。
算法的时间复杂度如何计算？
2楼：
关于时间复杂度的计算是按照运算次数来进行的，比如1题：
sum1( int n )
//n次
return (sum) ; //1次
} 最后总的次数为
1+（n+1）+n+n+1+1=3n+3
所以时间复杂度f（o）=n；（时间复杂度只管n的最高次方，不管他的系数和表达式中的常量）
其余的一样，不明白的可以来问我
3楼：匿名用户
求解算法的时间复杂度的具体步骤是：
⑴ 找出算法中的基本语句；
4楼：爱上鸟儿
一个算法花费的时间与算法中语句的执行次数成正比例，时间复杂度一般用o（f(x)）表示.
f(x)在简单程序中就是看有几个for循环，然后看看再它的判断语句，就是看看它执行了几次，f(x)=“执行的次数”。
像题中的（1）有一个for循环执行次数为n次，所以f(x)=n,时间复杂度就为o(n)
（2）有两个for循环执行次数为n*n,即n的平方，所以f(x)=n的平方，时间复杂度就是o(n的平方）。
（3）是递归，它也执行了n次所以它的时间复杂度就是o(n).
不过要注意时间复杂度的f(x)在有限次时就用具体数值表示，无限次时就用n，n的平方，log以2为底n的对数，其实很简单就是看n的最高次方，看n的最高次方等于几,f(x)就等于几。
5楼：匿名用户
就是程序执行次数和输入n的函数关系
1.o(n)
2.o(n平方)
3.o(n)
请问递归算法的时间复杂度如何计算呢?
6楼：木子青耶
递归算法的时间复杂度在算法中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，常用以下四种方法：
代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。
迭代法的基本步骤是迭代地递归方程的右端，使之成为一个非递归的和式，然后通过对和式的估计来达到对方程左端即方程的解的估计。
这个方法针对形如“t(n) = at(n/b) + f(n)”的递归方程。这种递归方程是分治法的时间复杂性所满足的递归关系。
即一个规模为n的问题被分成规模均为n/b的a个子问题，递归地求解这a个子问题，然后通过对这a个子间题的解的综合，得到原问题的解。
可以将某些递归方程看成差分方程，通过解差分方程的方法来解递归方程，然后对解作出渐近阶估计。
7楼：泡影果果
1、递归
是指对一个问题的求解，可以通过
同一问题的更简单的形式的求解来表示. 并通过问题的简单形式的解求出复杂形式的解. 递归是解决一类问题的重要方法.
递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的. 但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省. 以下讨论递归的时间效率分析方法，以及与非递归设计的时间效率的比较.
2、时间复杂度的概念及其计算方法
算法是对特定问题求解步骤的一种描述. 对于算法的优劣有其评价准则，主要在于评价算法的时间效率，算法的时间通过该算法编写的程序在计算机中运行的时间来衡量，所花费的时间与算法的规模n有必然的联系，当问题的规模越来越大时，算法所需时间量的上升趋势就是要考虑的时间度量。
算法的时间度量是依据算法中最大语句频度（指算法中某条语句重复执行的次数）来估算的，它是问题规模n的某一个函数f(n). 算法时间度量记作：t（n）=o（f（n）） 。
它表示随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度，简称时间复杂度[2]。
例如下列程序段：
（1）x=x+1;（2）for(i=1;i<=n;i++) x=x+1;（3）for(j=1;j<=n;j++) for(k=1;k<=n;k++) x=x+1. 以上三个程序段中，语句x=x+1的频度分别为1，n，n2，则这三段程序的时间复杂度分别为o（1），o（n），o（n2）。
求解过程为：先给出问题规模n的函数的表达式，然后给出其时间复杂度t（n）。
但是在现实程序设计过程中，往往遇到的问题都是比较复杂的算法，就不能很容易地写出规模n的表达式，也比较难总结其时间复杂度. 递归函数就是属于这种情况. 下面举例说明递归函数的时间复杂度的分析方法。
程序中的时间复杂度是怎么计算的？
8楼：匿名用户
算法复杂度的介绍，见百科：
http://baike.baidu.***/view/7527.htm
如何计算时间复杂度
9楼：du小悟
定义：如果一个问题的规模是n，解这一问题的某一算法所需要的时间为t(n)，它是n的某一函数 t(n)称为这一算法的“时间复杂性”。
当输入量n逐渐加大时，时间复杂性的极限情形称为算法的“渐近时间复杂性”。
我们常用大o表示法表示时间复杂性，注意它是某一个算法的时间复杂性。大o表示只是说有上界，由定义如果f(n)=o(n)，那显然成立f(n)=o(n^2)，它给你一个上界，但并不是上确界，但人们在表示的时候一般都习惯表示前者。
此外，一个问题本身也有它的复杂性，如果某个算法的复杂性到达了这个问题复杂性的下界，那就称这样的算法是最佳算法。
“大 o记法”：在这种描述中使用的基本参数是 n，即问题实例的规模，把复杂性或运行时间表达为n的函数。这里的“o”表示量级 (order)，比如说“二分检索是 o(logn)的”,也就是说它需要“通过logn量级的步骤去检索一个规模为n的数组”记法 o ( f(n) )表示当 n增大时，运行时间至多将以正比于 f(n)的速度增长。
这种渐进估计对算法的理论分析和大致比较是非常有价值的，但在实践中细节也可能造成差异。例如，一个低附加代价的o(n2)算法在n较小的情况下可能比一个高附加代价的 o(nlogn)算法运行得更快。当然，随着n足够大以后，具有较慢上升函数的算法必然工作得更快。
o(1)
temp=i;i=j;j=temp;
以 上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作t(n)=o(1)。如果算法的执行时 间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。
此类算法的时间复杂度是o(1)。
o(n^2)
2.1. 交换i和j的内容
sum=0； （一次）
for(i=1;i<=n;i++) （n次 ）
for(j=1;j<=n;j++) （n^2次 ）
sum++； （n^2次 ）
解：t(n)=2n^2+n+1 =o(n^2)
2.2.
for (i=1;i 解： 语句1的频度是n-1 语句2的频度是(n-1)*(2n+1)=2n^2-n-1 f(n)=2n^2-n-1+(n-1)=2n^2-2 该程序的时间复杂度t(n)=o(n^2). o(n) 2.3. a=0; b=1; ① for (i=1;i<=n;i++) ② 解： 语句1的频度：2, 语句2的频度： n, 语句3的频度： n-1, 语句4的频度：n-1, 语句5的频度：n-1, t(n)=2+n+3(n-1)=4n-1=o(n). o(log2n ) 2.4. i=1; ① while (i<=n) i=i*2; ② 解： 语句1的频度是1, 设语句2的频度是f(n), 则：2^f(n)<=n;f(n)<=log2n 取最大值f(n)= log2n, t(n)=o(log2n ) o(n^3) 2.5. for(i=0;i }解： 当i=m, j=k的时候,内层循环的次数为k当i=m时, j 可以取 0,1,...,m-1 , 所以这里最内循环共进行了0+1+... +m-1=(m-1)m/2次所以,i从0取到n, 则循环共进行了: 0+(1-1)*1/2+...+(n-1)n/2=n(n+1)(n-1)/6所以时间复杂度为o(n^3). 我 们还应该区分算法的最坏情况的行为和期望行为。如快速排序的最 坏情况运行时间是 o(n^2)，但期望时间是 o(nlogn)。通过每次都仔细 地选择基准值，我们有可能把平方情况 (即o(n^2)情况)的概率减小到几乎等于 0。 在实际中，精心实现的快速排序一般都能以 (o(nlogn)时间运行。 下面是一些常用的记法： 访问数组中的元素是常数时间操作，或说o(1)操作。一个算法 如 果能在每个步骤去掉一半数据元素，如二分检索，通常它就取 o(logn)时间。用strcmp比较两个具有n个字符的串需要o(n)时间 。 常规的矩阵乘算法是o(n^3)，因为算出每个元素都需要将n对 元素相乘并加到一起，所有元素的个数是n^2。 指数时间算法通常**于需要 求出所有可能结果。例如，n个元 素的集合共有2n个子集,所以要求出所有子集的算法将是o(2n)的 。指数算法一般说来是太复杂了，除非n的值非常小，因为，在 这个问题中增加一个元素就导致运行时间加倍。 不幸的是，确实有许多问题 (如著名 的“巡回售货员问题” )，到目前为止找到的算法都是指数的。如果我们真的遇到这种情况， 通常应该用寻找近似最佳结果的算法替代之。 1楼 mean有方法的 o什么，要知道，排序理论最快时间复杂度只能是nlogn，不能再快，这是有证明的。想要提高速度用c 函数库的qsort 如何对n个数进行排序，要求时间复杂度o，空间复杂度o 2楼 钟萌纳 题目 如何对n个不重复出现的整数序列进行排序 已知这些数的范围为 0 65535 要求时间...如何对n个数进行排序，要求时间复杂度o，空间复杂度o