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

算法 大约 1139 字

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

算法的时间复杂度

计算程序执行时间

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

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

时间频度

算法中语句的执行次数。

常见时间复杂度

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

常数阶 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(log2n)

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(n2)

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(n3)

三层n循环。

K 次方阶 O(nK)

Kn循环。

指数阶 O(2n)

平均时间复杂度

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

最坏时间复杂度

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

算法的空间复杂度

定义

算法所耗费的存储空间(内存)。

备注

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

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

参考

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

阅读 48 · 发布于 2021-02-02

————        END        ————

扫描下方二维码关注公众号和小程序↓↓↓

扫描二维码关注我
昵称:
随便看看 换一批