2.2大O表示法

算法时间度量指标

一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标
哪种操作跟算法的具体实现无关？
需要一种通用的基本操作来作为运行步骤的计量单位

• 赋值语句是一个合适的选择

一条赋值语句同时包含了（表达式）计算和（变量）存储两个基本资源仔细观察程序设计语言特性，除了与计算资源无关的定义语句外，主要就是三种控制流语句和赋值语句，而控制流仅仅起了组织语句的作用，并不实施处理。

赋值语句执行次数

1.分析SumOfN的赋值语句执行次数
2.对于“问题规模”n，赋值语句数量T(n)=1+n。

def sumOfN(n):
    theSum = 0 # 1
    for i in range(1, n+1): # n
        theSum = theSum + i
    return theSum

问题规模影响算法执行时间

问题规模：影响算法执行时间的主要因素
在前n个整数累计求和的算法中，需要累计的整数个数合适作为问题规模的指标前100,000个整数求和对比前1,000个整数求和，算是同一问题的更大规模
算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间

数量级函数 Order of Magnitude

基本操作数量函数T(n)的精确值并不是特别重要，重要的是T(n)中起决定性因素的主导部分
用动态的眼光看，就是当问题规模增大的时候，T(n)中的一些部分会盖过其它部分的贡献
数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分称作“大O”表示法，记作O(f(n))，其中f(n)表示T(n)中的主导部分

• 确定运行时间数量级大O的方法
  例：T(n)=1+n
  当n增大时，常数1在最终结果中显得越来越无足轻重所以可以去掉1，保留n作为主要部分，运行时间数量级就是O(n)
  例：T(n)=5n²+27n+1005
  当n很小时，常数1005其决定性作用但当n越来越大，n2项就越来越重要，其它两项对结果的影响则越来越小同样，n2项中的系数5，对于n2的增长速度来说也影响不大所以可以在数量级中去掉27n+1005，以及系数5的部分，确定为O(n²)

影响算法运行时间的其它因素

有时决定运行时间的不仅是问题规模
某些具体数据也会影响算法运行时间
分为最好、最差和平均情况，平均状况体现了算法的主流性能对算法的分析要看主流，而不被某几种特定的运行状况所迷惑

常见的大O数量级函数

1.通常当n较小时，难以确定其数量级
2.当n增长到较大时，容易看出其主要变化量级

image.png

f(n)	名称
1	常数
log(n)	对数
n	线性
n*log(n)	对数线性
n2	平方
n3	立方
2n	指数

• 从代码分析确定执行时间数量级函数
  代码赋值语句可以分为4个部分，这里第一个方框内T(n) = 3，第二个方框内T(n) = 3n²，第三个方框内T(n) = 2n，第四个方框内T(n) = 1
  T(n) = 3+3n²+2n+1 = 3n²+2n+4，估算数量级的话，仅保留最高阶项n²，去掉所有系数，数量级为O(n²)
  

其它算法复杂度表示法

• 大O表示法
  表示了所有上限中最小的那个上限。
• 大𝛀表示法
  表示了所有下限中最大的那个下限
  
• 大𝚹表示法
  如果上下限相同，那么就可以用大𝚹表示