当前位置:   article > 正文

【数据结构(邓俊辉)学习笔记】绪论01——复杂度度量_度量复杂度

度量复杂度

0.意图

算法的计算成本涵盖诸多方面,为确定计算成本的度量标准,不妨先从计算速度这一主要因素入手。具体地,如何度量一个算法所需的计算时间呢?

1. 时间复杂度

从保守估计的角度出发,在规模为n的所有输入(n! 种输入)选择执行时间最长者作为T(n),并以T(n)度量该算法的时间复杂度。

2. 渐进复杂度

在评价算法运行效率时,更关注其在处理更大规模问题时的表现。因为小规模问题所需的处理时间本来就相对更少,故此时不同算法的实际效率差异并不明显;而在处理更大规模的问题时,效率的些许差异都将对实际执行效果产生巨大的影响。这种着眼长远、更为注重考察成本的增长趋势的策略与方法,即所谓的渐进分析(asymptotic analysis)。
针对足够大的输入规模n,算法执行时间T(n)的渐进增长速度,应如何度量和评价呢?
需要执行的基本操作次数:T(n) = ?

3. 大O记号

在这里插入图片描述
在大O记号的意义下,

  1. 正的常系数可以忽略并等同于1。
  2. 多次项中的低此项均可忽略,只需保留最高此项。

可以看出,大O记号的性质的确体现了对函数总体渐进增长趋势和关注和刻画。

4. 最坏、最好与平均情况

大O记号实质上是对算法执行时间的一种保守估计,对于规模为n的任意输入,算法的运行时间都不会超过O(f(n))。比如”起泡排序算法“

void bubblesort1A( int A[], int n ) { //起泡排序算法(版本1A):0 <= n
   /*DSA*/int cmp = 0, swp = 0;
   bool sorted = false; //整体排序标志,首先假定尚未排序
   while ( !sorted ) { //在尚未确认已全局排序之前,逐趟进行扫描交换
      sorted = true; //假定已经排序
      for ( int i = 1; i < n; i++ ) { //自左向右逐对检查当前范围A[0, n)内的各相邻元素
         if ( A[i - 1] > A[i] ) { //一旦A[i - 1]与A[i]逆序,则
            swap( A[i - 1], A[i] ); //交换之,并
            sorted = false; //因整体排序不能保证,需要清除排序标志
            /*DSA*/swp++; printf ( "%3d: ", n ); print ( A, n, i - 1, i + 1 );
         }
         /*DSA*/cmp++;
      }
      n--; //至此末元素必然就位,故可以缩短待排序序列的有效长度
   }
   /*DSA*/ printf( "#comparison = %d, #swap = %d\n", cmp, swp );
} //借助布尔型标志位sorted,可及时提前退出,而不致总是蛮力地做n - 1趟扫描交换
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17

该算法由内、外两层循环组成。内循环从前向后,依次比较各对相邻元素,如有必要则将其交换。故在每一轮内循环中,需要扫描和比较n-1对元素,至多需要交换n-1对元素。元素的比较和交换都属于基本操作,故每一轮内循环至多需要执行2(n-1)次基本操作。外循环至多执行n-1轮。因此,总共需要执行的基本操作不会超过 2 ( n − 1 ) 2 2(n-1)^2 2(n1)2次。则有
T ( n ) = O ( 2 ( n − 1 ) 2 ) = O ( 2 n 2 − 4 n + 2 ) = O ( 2 n 2 ) = O ( n 2 ) T(n) =O(2(n-1)^2)=O(2n^2-4n+2)=O(2n^2)=O(n^2) T(n)=O(2(n1)2)=O(2n24n+2)=O(2n2)=O(n2)
复杂度 T ( n ) = O ( n 2 ) T(n)=O(n^2) T(n)=O(n2)意味着,该算法处理任何序列所需的时间绝不会超过O( n 2 n^2 n2)。称作最坏实例或最坏情况
对于某种序列如{1,2,3,4},甚至只需执行一轮,称作最好情况
有时也需要考查所谓的平均情况,也就是按照某种约定的概率分布,将规模为n的所有输入对应的计算时间加权平均
比较而言,”最坏情况复杂度“是人们最为关注且使用最多的,在一些特殊的场合甚至成为唯一标准。

5. 分摊分析

平均复杂度 是指在假定各种输入实例的出现符合某种概率分布之后,进而估算出的加权复杂度均值。将基于“待排序的元素服从独立均匀随机分布”这一假设,估算出快速排序算法在各种情况下的加权平均复杂度。

分摊复杂度 是纵观连续的足够多次操作,并将其间总体所需的运行时间分摊至各次操作。与平均复杂度的本质不同在于,这里强调,操作序列必须是的确能够真实发生的,其中各次操作之间应存在前后连贯的时序关系。

由此可见,前者不必考查加权平均的各种情况出现的次序,甚至其针对概率分布所做的假设未必符合真实情况;后者不再割裂同一算法或数据结构的各次操作之间的因果关系,更加关注其整体的性能。综合而言,基于后一尺度得出的分析结论,应该更符合于真实情况,也更为可信。

在这里插入图片描述

6.大Ω记号

如果存在正的常数c和函数g(n),使得对于任何n >> 2都有
T(n) ≥ c∙g(n)
在n足够大之后,g(n)给出了T(n)的一个渐进下界。记为:
T(n) = Ω(g(n))
大Ω记号是对算法执行效率的乐观估计,对于规模为n的任意输入,算法的运行时间都不低于Ω(g(n))。
比如,即便在最好情况下,起泡排序也至少需要T(n) = Ω(n)的计算时间。
至少需要对每个元素访问一次。否则,即便其余n - 1个整数业已排序,在未读取出该整数的准确数值之前,仍无法确定整体的排列次序。

7. 大θ记号

借助大O记号、大Ω记号,可以对算法的时间复杂度作出定量的界定,亦即,从渐进的趋势
看,T(n)介于Ω(g(n))与O(f(n))之间。若恰巧出现g(n) = f(n)的情况,则可以使用另一记
号来表示。
如果存在正的常数c1 < c2和函数h(n),使得对于任何n >> 2都有
c1∙h(n) ≤ T(n) ≤ c2∙h(n)
就可以认为在n足够大之后,h(n)给出了T(n)的一个确界。此时,我们记之为:
T(n) = θ(h(n))
它是对算法复杂度的准确估计,对于规模为n的任何输入,算法的运行时间T(n)都与θ(h(n))同阶。

大o记号、大Ω记号和大θ记号

需要笔记的朋友,可留言。
参考书籍
《数据结构》邓俊辉编著

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/码创造者/article/detail/1019473
推荐阅读
相关标签
  

闽ICP备14008679号