大O标记法与常见时间复杂度
2024年4月3日大约 2 分钟
算法 : 内功心法, 是解决问题的一种思想
时间复杂度
由于每台机器的性能有所差别,所有其执行相同代码的时间也长短不一,故而推出一种计量方式,统计代码执行基本运算(函数调用需要看其源码的基本运算
)的数量(n
) 来确定一个算法的优劣,其中基本运算的循环按乘法计算,顺序结构按加法计算,分支结构取最大值。
for a in range(0, 1000):
for b in range(0, 1000):
for c in range(0, 1000):
if a+b+c == 1000 and a**2 + b**2 + c**2:
print('a,b,c,: {}, {}, {}'.format(a,b,c))
上述代码的时间复杂度为
那么如果将上述代码中的 1000 改为 2000, 则
由于上述同样的代码由于不同的参数的 T 都不同,我们便将其统一成 N,这样上述代码的时间复杂度可以表示成:
同样的我们抓住其主要 “矛盾” ,观其大,再将其简化成
这样同一段代码的时间复杂度便不会根据其参数而发生改变了。
大 标记法
其实和求极限的原理相似,抓住问题的主要矛盾,忽略那些细枝末节,也就像前面的
时间复杂度的几条基本规则
基本步骤: 即只有常数项, 算作
基本结构顺序, 条件, 循环
- 顺序结构: 按加法运算
- 循环结构: 乘法
- 分支结构: 取最大值
判断一个算法效率, 往往只需要关注操作数量的最高次项, 其他次要的忽略
没特殊说明, 分析的时间复杂度都是最坏时间复杂度
常见的时间复杂度
名称 | ||
---|---|---|
常数阶 | ||
线性阶 | ||
平方阶 | ||
对数阶 | ||
立方阶 | ||
指数阶 |