数据结构课件：算法时间复杂度的概念.pptx

算法时间复杂度的概念

本讲要点为什么要考虑算法时间复杂度？什么是算法时间复杂度？如何计算算法时间复杂度？

（1）为什么要考虑算法时间复杂度？一种数据结构的优劣是由实现其各种操作的算法决定的。对数据结构的分析实质上就是对实现各种操作的算法进行分析。除了要验证算法是否能正确解决问题外，还需要对算法的效率进行评价。对于一个实际问题的解决，可以提出若干算法，那么如何从这些可行的算法中找出最有效的算法呢？或者有了一个解决实际问题的算法，如何来分析它的性能呢？这些问题需要通过算法分析来确定。通常，算法分析主要分析算法的时间代价和空间代价这两个主要指标。

（1）为什么要考虑算法时间复杂度？随着计算机功能的日益强大，程序的运行效率变得越来越不那么重要了吗？计算机功能越强大，人们就越想去尝试解决更复杂的问题。不仅需要算法，而且需要“好”的算法。在选择和设计算法时要有效率的观念，这一点比提高计算机本身的速度更为重要。

（2）什么是算法时间复杂度？问题规模的概念：是指输入量的多少，一般来说，它可以从问题描述中得到。一个事实：几乎所有的算法，对于规模更大的输入都需要运行更长的时间。运行算法所需要的时间是问题规模n的函数。要精确地用函数表示算法的运行时间是很困难的。算法时间分析度量的标准：不是针对实际执行时间精确算出算法执行的具体时间，而是针对算法中基本语句的执行次数做出估计。

（2）什么是算法时间复杂度？如何度量：引入时间复杂度（TimeComplexity）概念。算法中基本语句的重复执行次数是问题规模n的某个函数f(n)，算法的时间度量表示为O(f(n))。这里的“O”是英文“Order”的缩写，但并不代表“顺序”的意思，而是“阶数”的概念。它表示随着问题规模n的增大，算法执行时间增长率和f(n)增长率相同，称为算法的渐近时间复杂度，简称时间复杂度，记作T(n)=O(f(n))。例如f(n)=amnm+am-1nm-1+…+a1n+a0，则T(n)=O(nm)。f(n)与nm之比是一个不等于零的常数，即f(n)与nm的数量级相同。在计算算法时间复杂度时，可以忽略所有低次幂项和最高次幂项的系数。

（3）如何计算算法时间复杂度？1）for(i=1;i100;i++)s++;该程序段的语句执行次数是常量，时间复杂度记为O(1)，称为常量阶。2）for(i=0;in;i++)s+=i;该程序段基本语句“s+=i;”的执行次数f(n)=n，因此它的时间复杂度T(n)=O(f(n))=O(n)，称为线性阶。

（3）如何计算算法时间复杂度？3）for(i=0;in;i++) for(j=0;jn;j++) s++;f(n)=n+n+…+n=n2，时间复杂度T(n)=O(f(n))=O(n2)，称为平方阶。4）for(i=0;in;i++) for(j=i;jn;j++) s++;这是一个二重循环，基本语句“s++;”的执行次数

f(n)=n+(n-1)+(n-2)+……+2+1=n(n+1)/2，是n2数量级，因此时间复杂度T(n)=O(n2)。

（3）如何计算算法时间复杂度？5）for(i=1;i=n;i=2*i) s++;设该程序段基本语句“s++;”的执行次数为f(n)，则有2f(n)≤n，即f(n)≤log2n，因此该段程序的时间复杂度为O(log2n)，称为对数阶。

小结：求解算法时间复杂度的步骤1）找出算法中的基本语句。算法中执行次数最多的那条语句就是基本语句。通常是最内层循环的循环体。2）计算基本语句的执行次数的数量级。只需计算基本语句执行次数的数量级。这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数，这样能够简化算法分析，并且使注意力集中在最重要的一点上——增长率。3）用大O记号表示算法的时间性能。将基本语句执行次数的数量级放入大O记号中。