数据结构与算法(Python版)二:大 O 表示法

算法时间度量指标

一个算法所实施的操作数量或步骤数可作为独立于具体程序/机器的度量指标

哪种操作跟算法的具体实现无关?
需要一种通用的基本操作来作为运行步骤的计量单位

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

一条赋值语句同时包含了(表达式)计算和(变量)存储两个基本资源

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

问题规模:影响算法执行时间的主要因素

在前n个整数累计求和的算法中,需要累计的整数个数合适作为问题规模的指标

前100000个整数求和对比前1000个整数求和,算是一个问题的更大规模

算法分析的目标是要找出问题规模会怎么影响一个算法的执行时间

数量级函数

基本操作数量函数 T(n)的精确值并不是特别重要,重要的是T(n)中起决定性因素的主导部分

用动态的眼光看,就是当问题规模增大的时候,T(n)中的一些部分会盖过其他部分的贡献

数量级函数描述了T(n)中随着n增加而增加速度最快的主导部分

称作”大O“表示法,记作O(f(n)),其中f(n)表示T(n)中的主导部分

确定运行时间数量级大O的方法

例1:T(n)=1+n

当n增大时,常数1在最终结果中显得越来越无足轻重,所以可以去掉1,保留n作为主要部分,运行时间数量级就是O(n)

例2:T(n)=5n^2+27n+1005

当n很小时,常数1005起决定性作用
当n越来越大时,n^2越来越重要
同样n^2中的系数5,对于n^2的增长速度来说也影响不大
所以去掉27n+1005,以及系数5的部分,确定为O(n^2)

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

有时决定运行时间的不仅是问题规模

某些具体数据也会影响算法运行时间

分为最好、最差和平均情况,平均状况体现了算法的主流性能,对算法的分析要看主流,而不被某几种特定的运行状况所迷惑。

常见的大O数量级函数

通常当n较小时,难以确定其数量级

当n增长到较大时,容易看出其主要变化量级

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

从代码分析确定执行时间数量级函数

a = 5
b = 6
c = 10
for i in range(n):
    for j in range(n):
        x = i * i
        y = j * j
        z = i * j
for k in range(n):
    w = a * k + 45
    v = b * b
d = 33

T(n) = 3 + 3n^2+2n+1=3*n^2+2n+4
仅保留最高阶项n^2,去掉所有系数,数量级为O(n^2)

大O表示法

表示了所有上限中最小的那个上限

上一篇:1005. K 次取反后最大化的数组和


下一篇:经典面试题-python函数之默认参数