1.
时间频度一个算法执行所耗费的时间,从理论上是不能算出来的,必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试,只需知道哪个算法花费的时间多,哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例,哪个算法中语句执行次数多,它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。
2.举例说明:
【例3.9】交换i和j的内容。
Temp=i;
i=j;
j=temp;
以上三条单个语句的频度均为1,该程序段的执行时间是一个与问题规模n无关的常数。算法的时间复杂度为常数阶,记作T(n)=O(1)。
如果算法的执行时间不随着问题规模n的增加而增长,即使算法中有上千条语句,其执行时间也不过是一个较大的常数。此类算法的时间复杂度是O(1)。
【例3.10】变量计数之一。
(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)=n2,所以该程序段的时间复杂度为T(n)=O(n2)。
当有若干个循环语句时,算法的时间复杂度是由嵌套层数最多的循环语句中最内层语句的频度f(n)决定的。
【例3.11】变量计数之二。
(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(n3/6+低次项)=O(n3)。
总结:计算算法的时间复杂度首先要计算出该算法执行的次数(频度),再与其他的语句进行比较。最大的就是该算法的时间复杂度
相关推荐
数据结构与算法笔记:时间复杂度和空间复杂度
这是数据结构算法课程中算复杂度的作业及答案。
数据结构算法时间复杂度的计算.doc
数据结构的基本概念和术语,算法的时间复杂度,讲述了数据结构的一些概念点,也就是最基本的一些东西,还有如何计算算法的时间复杂度之类的一些问题及举例
数据结构时间复杂度
对若干个数据进行操作,实现快速排序、选择排序、直接插入排序、堆排序算法时间复杂度的比较;并在排序数据中快速查找某一数据,给出查找是否成功,以及数据所在的位置信息。
速查表:常用算法和时间复杂度,算法数据结构 五大常用算法
时间复杂度和空间复杂度,大O表示法【数据结构和算法入门2】
根号n段归并排序算法时间复杂度分析过程: 1.合并 根号n向下取整 段子数组使用的是自底向上两两归并的策略 2.根号n段归并排序算法时间复杂度的数学推导
试完成求有向图的强连同分量的算法,并分析算法的时间复杂度
算法-数据结构和算法-1-算法的引入和算法时间复杂度.rar
数据结构,算法的时间复杂度计算方法,算法算法时间复杂度
数据结构与算法.DOC 1 算法 算法:是指解题方案的准确而完整的...算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。
算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)
数据结构与算法复杂度速查表是一款对常用数据结构与算法的复杂程度进行快速查询的表格。 数据结构与算法复杂度速查表演示图:
算法复杂度:算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 2 数据结构的基本基本概念 数据结构研究的三个方面: (1)...
算法的复杂度主要包括:时间复杂度、空间复杂度 6. 算法的时间复杂度:指执行算法所需要的计算工作量 7. 算法的空间复杂度:指执行这个算法所需要的内存空间 8. 数据结构主要研究:数据的逻辑结构、数据的存储结构...
算法的复杂度主要包括:时间复杂度、空间复杂度 6. 算法的时间复杂度:指执行算法所需要的计算工作量 7. 算法的空间复杂度:指执行这个算法所需要的内存空间 8. 数据结构主要研究:数据的逻辑结构、数据的存储结构...
数据结构、算法总结、学习算法的时间复杂度、空间复杂度、分析算法特点以及应用、Java面试难题、Android面试难题