算法的时间复杂度分析

2019-03-17  本文已影响0人  kopshome

学习算法的读书笔记
据说, 学习算法时, 时间复杂度是精髓, 把时间复杂度搞清楚, 算法就学成一半了?

为什么要学习复杂度分析

算法写完之后, 通过实际测量, 监控, 就可以得到比较准确的时间, 空间消耗, 那为什么还要学习复杂度呢? 这种办法是正确的, 但是这叫做事后分析法. 这种办法有很大局限.

同一数据量, 同一代码, 在不同环境, 运行结果肯定是不一样的. 甚至运行的结果截然相反, 反差巨大

同一环境, 同一代码, 随着数据规模的变化, 并不一定是线性趋势. 例如排序, 数据的规模, 质量都有很大的影响, 如果数据恰好有序, 那么进行一次冒泡排序用时就非常短.

综上所述, 我们需要一个不用具体去测试, 就可以粗略的估计出算法的执行效率的办法. 这就是所谓的时间, 空间复杂度分析方法.

大 O 复杂度分析法

对于算法的执行效率, 简单说就是代码的执行时间, 但是怎么在不允许代码的情况下, 一下看出一段代码的执行时间呢?


    /**
     * 计算 1,2,3...n 的加和
     *
     * @param n
     * @return
     */
    public static int plus(int n) {
        int sum = 0;
        for (int i = 1; i <= n; i++) {
            sum = sum + i;
        }
        return sum;
    }

在粗略估计的情况下, 假设每行代码的计算时间是一样的, 那么执行时间是多久? 如果假设每一行代码的运行时间定义为unit.

代码int sum=0运行时间为1*unit, sum = sum + i这行代码的运行总时间为n*unit,return sum;运行时间为1*unit, 那么最终就可以算出这段代码的总运行时间为 (2+n)*unit. 这时候就可以得出一个结论: 这段代码的执行时间T(n)与代码的执行次数成正比

总结为公式就是 :

{ T }_{ n }=O(f(n))

T(n)的含义是代码的执行时间, 其中n为数据规模的大小.f(n)为每行代码的执行的次数总和. 因为这是一个公式所以用f(n)表示. 那么O, 就是T(n)与f(n)成正比. 这就是大O时间复杂度表示法. 它并不是表示代码的执行时间, 而是表示代码随数据规模增长的变化趋势! 这就是时间复杂度.

如果n很大,例如1000000000, 那么(2+n)中的2, 就可以忽略了, 所以上面公式就可以是: T(n)=O(n). 即它的时间复杂度为 n. 总结起来就是: 公式中的低阶, 系数, 常量值都可以忽略, 因为他们不会左右增长的趋势,

时间复杂度分析

下面会有三个办法来帮助你进行时间复杂度分析:

1. 只关注循环次数最多的代码

上面的代码中, 循环次数最多的代码无疑就是sum = sum + i;, 那么我们只要关注他就可以了,时间复杂度就是O(n), 例如下面的伪代码:


for(int j = 1; j<=n: j++){

        for (int i = 1; i <= n; i++) {
            sum = sum + i;
        }

}

代码 sum = sum + i;的循环次数是n的平方, 那么时间复杂度就是O(n^2)

2. 总的复杂度就是量级最大那段代码的复杂度

下面的伪代码:


for(int j = 1; j<=n: j++){

        other = other + j;  

        for (int i = 1; i <= n; i++) {
            sum = sum + i;
        }

}

代码other = other + j;运行次数为n, 而sum = sum + i;运行次数为n2,所以最后的复杂度也是O(n2)

3. 嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

如果循环里面只有一行代码,然后这行代码调用了另外一个函数f(), 这个f()也是一层循环, 那么最后的复杂度就是他们的乘积

上面的技巧其实不用刻意去记, 因为多看就慢慢理解了

几种常见的复杂度

常见的复杂度如下:


# 常量阶

O(1)

# 对数阶

O(logn)

# 线性阶

O(n)

# 线性对数阶

O(nlogn)

# 平方阶,立方阶....M次方阶

O(n^2),O(n^3),O(n^m)

# 指数阶

O(2^n)

# 阶乘阶

O(n!)

如果按多项式和费多项式来分类, 那么只有倒数两个是多项式,其他的为单项式. 数据规模增大的时候, 非多项式的执行时间会急剧增加, 所以非多项式复杂度的算法是非常抵消的. 下面调一个例子来说明上面的复杂度.

  1. O(nlogn) 或 O(logn)

看下面的代码片段:


        int i = 1;
        while (i <= n) {
            i = i * 2;
        }

根据之前讲的原则, 我们只计算 i = i * 2;的执行次数, i的初始值是1, 每循环一次, 它就乘以2, 直到 小于或等于n时, 停止计算, 那么将i的值变化过程总结一下就是:

{ 2 }^{ 0 },{ 2 }^{ 1 },{ 2 }^{ 2 } ... { 2 }^{ k }

也就是说当{ 2 }^{ k }时候等于n, 那么直到k是多少, 就知道了这行代码的运行次数.计算k值就很简单了, 高中数学水平就可以算出 k=\log _{ 2 }{ n }, 不管是以多少为底, 只要是一个常量, 我们就可以将它忽略, 将这一复杂度统一定为: O(logn). 所以即使将i = i * 2;变为i = i * 3;, 它的时间复杂度也是O(logn).

最好, 最坏时间复杂度

看下面的代码:


    public static int find(int[] array, int m) {
        int n = array.length;
        for (int i = 0; i < n; i++) {
            if (array[i] == m){
                return i;
            }
        }
        return -1;
    }

代码的含义为: 查找数组中, 值为m的角标, 如果找到了, 停止程序并返回其下标. 很容易可以看出. 如果第一次循环就找到了, 此时的复杂度就是O(1), 如果没有此值或此值在数组最后位置上, 此时的复杂度就是O(n), 有最好, 最坏复杂度, 那么平均复杂度该是多少?

平均时间复杂度

还是上面的例子, 查找m在数组中的位置, 可以分为两类可能:

第一种情况下, 所有的次数加起来应该等于 1+2+3+4+ ... +n, 第二中情况, 次数是个定值 n. 所以这两大种情况加起来, 总共的执行次数是: 1+2+3+4+ ... +n+n

两种情况中, m出线在数组中的位置, 自然就是有n+1中可能. 总的次数, 除以n+1, 就是它的平均复杂度. 总结成公式就是:

\frac { 1+2+3+4+...+n+n }{ n+1 } =\frac { n(n+3) }{ 2(n+1) }

去掉低阶, 常量之后, 上面的公式最终就简化为 O(n)

上一篇 下一篇

猜你喜欢

热点阅读