算法的时间复杂度和空间复杂度

算法的时间复杂度和空间复杂度

算法的时间复杂度

计算程序执行时间

事后统计：打印程序的耗时时间，依赖于计算机硬件等因素，需在同一台计算机相同状态运行程序才准确。

事前估算：分析算法的时间复杂度来判断算法的优劣。

时间频度

算法中语句的执行次数。

常见时间复杂度

时间复杂度依次从小到大。

常数阶 O(1)

只要没有循环，不管多少行代码都是O(1)。

func ConstantTime(i, j int) int {
    var a,b int
    if i%2 == 0 {
        a = i+j
    }
    if j%2 == 1 {
        b = i+j
    }
    return a+b
}

对数阶 O(log₂n)

func LogarithmicTime(n int) {
    i := 1
    for i < n {
        i = i * 2
    }
}

线性阶 O(n)

func LinearTime(n int) {
    // 几百万行代码
    for i := 0; i < n; i++ {
        // 几百万行代码
    }
    // 几百万行代码
}

线性对数阶 O(n log n)

func LinearithmicTime(m, n int) {
    for i := 0; i < m; i++ {
        j := 1
        for j < n {
            j = j * 2
        }
    }
}

平方阶 O(n²)

func QuadraticTime(n int)  {
    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            fmt.Printf("%d\t%d", i, j)
        }
        fmt.Println()
    }

}

立方阶 O(n³)

三层n循环。

K 次方阶 O(n^K)

K层n循环。

指数阶 O(2ⁿ)

平均时间复杂度

所有可能的输入以等概率的时间出现的情况。

最坏时间复杂度

一般讨论的时间复杂度都是最坏时间复杂度。最坏情况下算法运行时间的边界。

算法的空间复杂度

定义

算法所耗费的存储空间（内存）。

备注

快速排序和归并排序占用较多的存储单元。

Redis，基数排序，二级缓存，三级缓存，都是属于空间换时间。

参考

https://en.wikipedia.org/wiki/Time_complexity