算法复杂度分析(上)

daklqw 2019-06-28

为什么需要算法复杂度分析?

首先,这和研究数据结构和算法的目的有关——“快”而“省”的解决问题。那么如何衡量算法的性能呢?就需要算法复杂度分析。

其次,除了算法复杂度分析,还有一种方法可以衡量复杂度,那就是“事后统计法”,即直接运行程序,统计需要的时间和空间。但是,这种方法有两个问题:

1)结果非常依赖于测试环境。比如,用 Core i3 和用 Core i8 运行程序所需的时间是不同的;

2)结果受测试规模的影响特别大。比如,对有序数组进行排序的时间比对逆序数组排序的时间短;对于小规模数据而言,插入排序所需时间比快速排序要短。

所以,就需要有一种不用具体测试数据,也能估计算法执行效率的方法,就是算法复杂度分析,包括时间、空间复杂度分析。

大 O 复杂度表示法

大 O 复杂度表示法可以归纳成下面一句话:

所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。

T(n) = O(f(n))。其中,f(n) 表示代码的执行次数之和。大 O 符号(Big O notation)是用于描述函数渐进行为的数学符号,它代表“order of...”(...阶)。

例如,对于代码:

function foo (n) {
    var i = 0;
    var j = 0;
    for (; i < n; i++) {
        j += i;
    }
}

假设每行代码的执行时间一样,为 unit_time。则第 2、3 行执行时间均为 1 unit_time,第 4、5 行代码执行时间均为 n unit_time,整个函数的执行时间 T(n) = (2n + 2) * unit_time。用大 O 复杂度表示法表示即为 T(n) = O(2n + 2)

注意,大 O 时间复杂度并不具体表示代码真正的执行时间,而是表示代码执行时间随数据规模增长的变化趋势。所以,它也叫渐进时间复杂度,简称时间复杂度。

当 n 很大时,不左右增长趋势的低阶、常量、系数均可忽略。所以,上面例子中的时间复杂度为 O(n)

时间复杂度分析

时间复杂度分析有下面几个原则:

1)只关注循环执行次数最多的一段代码;

2)加法原则:总复杂度等于量级最大的那段代码的复杂度。用公式表示即为:T1(n) = O(f(m)),T2(n) = O(g(n)),T1(n) + T2(m) = O(max(f(n), g(m)))

3)乘法原则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘机。用公式表示即为:T1(n) = O(f(m)),T2(n) = O(g(n)),T1(n) * T2(m) = O(f(n) * g(m))

常见的时间复杂度有以下几种:

1)常量阶:O(1)

2)对数阶:O(logn)

3)线性阶:O(n)

4)线性对数阶:O(nlogn)

5)平方阶:O(n ^ 2)

6)指数阶:O(2 ^ n)

7)阶乘阶:O(n!)

其中,1)-5)为多项式量级;6)、7)为非多项式量级,所对应的算法问题被称为非确定多项式问题(NP 问题,Non-Deterministic Polynomial)。

空间复杂度分析

空间复杂度全称为渐进空间复杂度(asymptostic space complexity)。空间复杂度较为简单,常见的空间复杂度为 O(1)O(n)O(n ^ 2)

最后,用几种复杂度的坐标图作为结尾:

算法复杂度分析(上)


首发于微信公众号《代码写完了》

算法复杂度分析(上)

相关推荐