算法的时间复杂度举例说明

① 算法复杂度的时间复杂度

（1）时间频度
一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。
（2）时间复杂度
在刚才提到的时间频度中，n称为问题的规模，当n不断变化时，时间频度T(n)也会不断变化。但有时我们想知道它变化时呈现什么规律。为此，我们引入时间复杂度概念。
一般情况下，算法中基本操作重复执行的次数是问题规模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)=n^2+3n+4与T(n)=4n^2+2n+1它们的频度不同，但时间复杂度相同，都为O(n^2)。
按数量级递增排列，常见的时间复杂度有：
常数阶O(1),对数阶O(log2n)(以2为底n的对数，下同),线性阶O(n),
线性对数阶O(nlog2n),平方阶O(n^2)，立方阶O(n^3),...，
k次方阶O(n^k),指数阶O(2^n)。随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。
算法的时间性能分析
（1）算法耗费的时间和语句频度
一个算法所耗费的时间=算法中每条语句的执行时间之和
每条语句的执行时间=语句的执行次数(即频度(Frequency Count))×语句执行一次所需时间
算法转换为程序后，每条语句执行一次所需的时间取决于机器的指令性能、速度以及编译所产生的代码质量等难以确定的因素。
若要独立于机器的软、硬件系统来分析算法的时间耗费，则设每条语句执行一次所需的时间均是单位时间，一个算法的时间耗费就是该算法中所有语句的频度之和。
求两个n阶方阵的乘积 C=A×B,其算法如下:
# define n 100 // n 可根据需要定义,这里假定为100
void MatrixMultiply(int A[a]，int B [n][n]，int C[n][n])
{ //右边列为各语句的频度
int i ,j ,k;
(1) for(i=0; i<n;i++) n+1
(2) for (j=0;j<n;j++) { n(n+1)
(3) C[i][j]=0; n2
(4) for (k=0; k<n; k++) n2(n+1)
(5) C[i][j]=C[i][j]+A[i][k]*B[k][j];n3
}
}
该算法中所有语句的频度之和(即算法的时间耗费)为：
T(n)=2n3+3n2+2n+1 (1.1)
分析：
语句(1)的循环控制变量i要增加到n，测试到i=n成立才会终止。故它的频度是n+1。但是它的循环体却只能执行n次。语句(2)作为语句(1)循环体内的语句应该执行n次，但语句(2)本身要执行n+1次，所以语句(2)的频度是n(n+1)。同理可得语句(3)，(4)和(5)的频度分别是n2，n2(n+1)和n3。
算法MatrixMultiply的时间耗费T(n)是矩阵阶数n的函数。
（2）问题规模和算法的时间复杂度
算法求解问题的输入量称为问题的规模(Size),一般用一个整数表示。
矩阵乘积问题的规模是矩阵的阶数。
一个图论问题的规模则是图中的顶点数或边数。
一个算法的时间复杂度(Time Complexity, 也称时间复杂性)T(n)是该算法的时间耗费，是该算法所求解问题规模n的函数。当问题的规模n趋向无穷大时，时间复杂度T(n)的数量级(阶)称为算法的渐进时间复杂度。
算法MatrixMultiply的时间复杂度T(n)如(1.1)式所示，当n趋向无穷大时，显然有T(n)~O(n^3);
这表明，当n充分大时，T(n)和n^3之比是一个不等于零的常数。即T(n)和n^3是同阶的，或者说T(n)和n^3的数量级相同。记作T(n)=O(n^3)是算法MatrixMultiply的渐近时间复杂度。
（3）渐进时间复杂度评价算法时间性能
主要用算法时间复杂度的数量级(即算法的渐近时间复杂度)评价一个算法的时间性能。
算法MatrixMultiply的时间复杂度一般为T(n)=O(n^3)，f(n)=n^3是该算法中语句(5)的频度。下面再举例说明如何求算法的时间复杂度。
交换i和j的内容。
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为1，该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶，记作T(n)=O(1)。
注意：如果算法的执行时间不随着问题规模n的增加而增长，即使算法中有上千条语句，其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
变量计数之一：
(1) x=0;y=0;
(2) for(k-1;k<=n;k++)
(3) x++;
(4) for(i=1;i<=n;i++)
(5) for(j=1;j<=n;j++)
(6) y++;
一般情况下，对步进循环语句只需考虑循环体中语句的执行次数，忽略该语句中步长加1、终值判别、控制转移等成分。因此，以上程序段中频度最大的语句是(6)，其频度为f(n)=n^2，所以该程序段的时间复杂度为T(n)=O(n^2)。
当有若干个循环语句时，算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
变量计数之二：
(1) x=1;
(2) for(i=1;i<=n;i++)
(3) for(j=1;j<=i;j++)
(4) for(k=1;k<=j;k++)
(5) x++;
该程序段中频度最大的语句是(5)，内循环的执行次数虽然与问题规模n没有直接关系，但是却与外层循环的变量取值有关，而最外层循环的次数直接与n有关，因此可以从内层循环向外层分析语句(5)的执行次数：
则该程序段的时间复杂度为T(n)=O(n^3/6+低次项)=O(n^3)。
（4）算法的时间复杂度不仅仅依赖于问题的规模，还与输入实例的初始状态有关。
在数值A[0..n-1]中查找给定值K的算法大致如下：
(1)i=n-1;
(2)while(i>=0&&(A[i]!=k))
(3) i--;
(4)return i;
此算法中的语句(3)的频度不仅与问题规模n有关，还与输入实例中A的各元素取值及K的取值有关:
①若A中没有与K相等的元素，则语句(3)的频度f(n)=n；
②若A的最后一个元素等于K,则语句(3)的频度f(n)是常数0。

② 算法的时间复杂度怎样计算举例子详细说明，谢谢。

循环次数搞清，时间复杂度自然就出来了。
for( i = 1; i <= n; ++ i )
for( j = 1; j <= i; ++ j )
外循环n次，对应每次外循环，内循环次数为1.2.3.4....n次,循环总次数 : n( n + 1 )/2
因此复杂度为O(n2)

③ 什么是算法的时间复杂度 画图说明

比如：
一个for循环
for（i=0; i<n;i++）
{}
这个算法的复杂性就是n，或者说是线性的.
再比如
for（i=0; i<n;i++）
{
for（j=0; j<n;j++）{
}

}
这个算法的复杂性就是n的平方
希望我说的还算详细

④ 1.3 请说明下列算法的时间复杂度.

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)。
为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。
首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。
先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。
具有L片树叶的二叉树的深度至少是logL。
所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。

⑤ 请问递归算法的时间复杂度如何计算呢

递归算法的时间复杂度在算法中，当一个算法中包含递归调用时，其时间复杂度的分析会转化为一个递归方程求解，常用以下四种方法：

1.代入法(Substitution Method)

代入法的基本步骤是先推测递归方程的显式解，然后用数学归纳法来验证该解是否合理。

2.递归程序设计是程序设计中常用的一种方法，它可以解决所有有递归属性的问题，并且是行之有效的.

3.但对于递归程序运行的效率比较低，无论是时间还是空间都比非递归程序更费，若在程序中消除递归调用，则其运行时间可大为节省.

⑥ 什么是算法的时间复杂度

是说明一个程序根据其数据n的规模大小 所使用的大致时间和空间
说白了 就是表示 如果随着n的增长 时间或空间会以什么样的方式进行增长

例
for(int i = 0; i < n;++i)
;
这个循环执行n次 所以时间复杂度是O(n)

for(int i = 0; i< n;++i)
{
for(int j = 0; j< n;++j)
;
}
这嵌套的两个循环 而且都执行n次
那么它的时间复杂度就是 O(n^2)

时间复杂度只能大概的表示所用的时间
而一些基本步骤 所运行的时间不同 我们无法计算 所以省略
如

for(int i = 0;i < n;++i)
a = b;
和
for(int i = 0;i < n;++i)
;
这个运行的时间当然是第二个快 但是他们的时间复杂度都是 O(n)
判断时间复杂度看循环

⑦ 如何计算时间复杂度

1、先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出T（n）的同数量级（它的同数量级有以下：1，Log2n ，n ，nLog2n ，n的平方，n的三次方，2的n次方，n！），找出后，f（n）=该数量级，若T(n)/f(n)求极限可得到一常数c，则时间复杂度T（n）=O（f（n））。

2、举例

for（i=1;i<=n;++i）

{for(j=1;j<=n;++j)

{c[ i ][ j ]=0; //该步骤属于基本操作 执行次数：n的平方次

for(k=1;k<=n;++k)

c[ i ][ j ]+=a[ i ][ k ]*b[ k ][ j ]; //该步骤属于基本操作 执行次数：n的三次方次}}

则有 T（n）= n的平方+n的三次方，根据上面括号里的同数量级，我们可以确定 n的三次方为T（n）的同数量级

则有f（n）= n的三次方，然后根据T（n）/f（n）求极限可得到常数c

则该算法的 时间复杂度：T（n）=O（n的三次方）

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

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

关于对其的理解

《数据结构（C语言版）》 ------严蔚敏 吴伟民编着 第15页有句话“整个算法的执行时间与基本操作重复执行的次数成正比。”

基本操作重复执行的次数是问题规模n的某个函数f(n)，于是算法的时间量度可以记为：T(n) = O(f(n))

如果按照这么推断，T(n)应该表示的是算法的时间量度，也就是算法执行的时间。

而该页对“语句频度”也有定义：指的是该语句重复执行的次数。

如果是基本操作所在语句重复执行的次数，那么就该是f(n)。

上边的n都表示的问题规模。

⑧ 算法时间复杂度的计算例题

第一题：
int i=1,k=100这条语句算法步数是2步,执行频率是1；
循环中, k=k+1;这条语句每次算法步数是1；执行频率是n/2-1; i+=2这条语句每次算法步数是1；执行频率是n/2-1;
所以算法复杂度为1*（n/2-1）+1*（n/2-1）+2=n=o(n);

⑨ 请说明下列算法的时间复杂度。

（1）O(n)。外层for循环O(n)；内层for循环O(1)，因为是常数个循环；x+=2为O(1)。则总的时间复杂度为O(n)。
（2）O(n^2)。外层for循环O(n)；内层for循环O(n)；两者都是线性时间复杂度。x++为O(1)。则总的时间复杂度为O(n^2)。

⑩ 算法时间复杂度的分析

不是呢。
关键要看n的大小和常量系数。
比如： O(N)的算法实际是20n， 而O(n^2)的算法实际是n^2
当输入数据规模n=10的时候，前者 是20*10 = 200 > 10^2 = 100.