ansible 一些基本使用方法的记录

衡量一个算法的效率.最直接有效的办法就是执行一遍,查看执行时间.但是更客观的方法是计算时间复杂度,并用”大O记法”表示

计算时间复杂度的基本原则

1. 基本操作,只有常数项,时间复杂度为O(1)
2. 顺序结构，按加法进行计算
3. 循环结构，按乘法进行计算
4. 分支结构，取最大值
5. 判断一个算法的效率只需要关注操作数量的最高次项，其它可以忽略
6. 分析的算时间复杂度一般都是指最坏时间复杂度

常见时间复杂度

函数	阶	通俗术语
5	O(1)	常数阶
$5\log_2{^n} + 2$	O($\log^n$)	对数阶
$3n + 5$	O($n$)	线性阶
$3n\log_2{^n} + 2n + 5$	O($n\log^n$)	$n\log^n$阶
$3n^2 + 2n + 1$	O($n^2$)	平方阶
$3n^3 + 2n^2 + n +1 $	O($n^3$)	立方阶
$2^n$	O($2^n$)	指数阶

所消耗的时间从低到高依次为:

O(1) < O($\log^n$) < O(n) < O($n\log^n$)) < O($n2$) < O($n^3$) < O($2^n$)

计算时间复杂度的案例

O($n^2$)

def test(n):
    # 一次
    sum = 0
    # n 次
    for i in range(n):
        # n 平方次
        for j in range(n):
            # n 平方次
            sum += 1
    return sum

T(n) = 1 + n + $n^2$ + $n^2$ = O($n^2$)

O($logn$)

def test(n):
    i = 1
    while i < n :
        i *= 2
    return i

每次循环 i 都 乘 2,所以设运算 x 次 则有 $2^x <= n$, 则 x = $\log_2{^n}$
T(n) = 1 + $\log_2{^n}$ = O($logn$)

Python 中的list和dict常用操作的效率

list 操作

dict 操作