算法 : 内功心法, 是解决问题的一种思想

时间复杂度 $T(n)$

由于每台机器的性能有所差别，所有其执行相同代码的时间也长短不一，故而推出一种计量方式，统计代码执行基本运算（函数调用需要看其源码的基本运算）的数量（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))

上述代码的时间复杂度为 $T = 1000 * 1000 * 1000 * 2$ 那么如果将上述代码中的 1000 改为 2000， 则 $T = 2000 * 2000 * 2000 * 2$ 由于上述同样的代码由于不同的参数的 T 都不同，我们便将其统一成 N，这样上述代码的时间复杂度可以表示成： $T = N * N * N * 2$ 同样的我们抓住其主要 “矛盾” ，观其大，再将其简化成 $T= N^3$ 这样同一段代码的时间复杂度便不会根据其参数而发生改变了。

大 $O$ 标记法 $O()$

其实和求极限的原理相似，抓住问题的主要矛盾，忽略那些细枝末节，也就像前面的 $T$的最后的样子。

时间复杂度的几条基本规则

1. 基本步骤: 即只有常数项, 算作 $O(1)$
2. 基本结构顺序, 条件, 循环
   • 顺序结构: 按加法运算
   • 循环结构: 乘法
   • 分支结构: 取最大值
3. 判断一个算法效率, 往往只需要关注操作数量的最高次项, 其他次要的忽略
4. 没特殊说明, 分析的时间复杂度都是最坏时间复杂度

常见的时间复杂度

$T$	$O$	名称
$12$	$O(1)$	常数阶
$2n+3$	$O(n)$	线性阶
$3n^2+2n+1$	$O(n^2)$	平方阶
$5log2n+20$	$O(log(n))$	对数阶
$2n+3nlog2n+19$	$O(nlog(n))$	$nlog(n)$ 阶
$6n^3+2n^2+3n+4$	$O(n^3)$	立方阶
$2^n$	$O(2^n)$	指数阶

$$O(1) < O(log(n)) < O(n) < O(nlog(n)) < O(n^2)< O(n ^ 2log(n)) < O(n^3) < O(2^n) < O(n!) < O(n^n)$$

版权所有

版权归属：liushaofeng

许可证：署名 4.0 国际 (CC-BY-4.0)