Skip to content

Latest commit

 

History

History
100 lines (75 loc) · 5.23 KB

02.算法基础导论.md

File metadata and controls

100 lines (75 loc) · 5.23 KB
Raw

目录介绍

  • 01.为何要复杂度分析
  • 02.大O复杂度表示法
    • 2.1 先分析两个案例
    • 2.2 总结案例的规律

好消息

  • 博客笔记大汇总【16年3月到至今】，包括Java基础及深入知识点，Android技术博客，Python学习笔记等等，还包括平时开发中遇到的bug汇总，当然也在工作之余收集了大量的面试题，长期更新维护并且修正，持续完善……开源的文件是markdown格式的！同时也开源了生活博客，从12年起，积累共计N篇[近100万字，陆续搬到网上]，转载请注明出处，谢谢！
  • 链接地址：https://github.com/yangchong211/YCBlogs
  • 如果觉得好，可以star一下，谢谢！当然也欢迎提出建议，万事起于忽微，量变引起质变！

01.为何要复杂度分析

  • 把代码跑一遍，通过统计、监控，就能得到算法执行的时间和占用的内存大小。为什么还要做时间、空间复杂度分析呢？
    • 首先肯定的说，这种评估算法执行效率的方法是正确的。很多书籍管这种方法叫“事后统计法”。但是这种方法有很大的局限性：
      • 测试结果非常依赖测试环境：如测试环境中的硬件对测试结果影响很大。
      • 测试结果受数据规模的影响很大。如小规模的数据，插入排序反而比快速排序快。
  • 使用复杂度分析有什么好处？
    • 需要一个不用具体数据来测试，就可以粗略的估算执行效率的方法。

02.大O复杂度表示法

2.1 先分析两个案例

  • 算法的执行效率，粗略的讲，就是算法的执行时间。
  • 例子1： 
    //这里有段简单的代码，求1到n的累加和。
int cla(int n){
    int sum = 0;
    for (int i=1 ;i<=n; i++){
        sum = sum + 1;
    }
    return sum;
}
    • 现在我们来估算下，上述代码的执行时间：尽管每行代码对应cpu执行的个数、执行的时间都不一样，但是我们这里只是粗略的估计，所以我们可以假设每行代码执行的时间都一样，都为unit_time。在这个假设的基础上，我们进行分析！
    • 第2、3行都执行了一次，第4、5行都执行了n次。所以这段代码总执行2unit_time+2nunit_time。可以看出代码的执行时间（T(n)）与代码的执行次数成正比。
  • 例2： 
    int cal(int n){
    int sum = 0;
    int i = 1; 
    int j = 1;
    for(; i<= n ;i++){
        j = 1;
        for(; j <= n ; j++){
            sum = sum + i*j;
        }
    }
}
    • 我们依旧按照例1中的方法进行分析。 2、3、4 行代码分别需要 1 个 unit_time 的执行时间，第 5、6 行都运行了 n 遍，所以需要 2n*unit_time 的执行时间，第 7、8 行代码循环执行了 n^2遍，所以需要 2n^2 * unit_time 的执行时间。所以，整段代码总的执行时间 T(n) = (2n^2+2n+3)*unit_time。
  • 通过两个例子，我们可以得出一个规律：
    • 所有代码的执行时间T(n)与每行代码的执行次数n成正比。

2.2 总结案例的规律

  • 可以把这个规律总结成一个公式。注意，大 O 就要登场了！
    • T(n)=O(f(n))
    • 来解释一下这个公式。T(n)表示代码的执行时间；n表示数据规模的大小；f(n)表示每行代码执行次数的总和。因为这是一个公式，所以用f(n)表示。公式中的O，表示代码的执行时间T(n)与f(n)表达式成正比。
  • 得出结论
    • 所以，第一个例子中Tn=O(2n+1)，第二个例子中的Tn=O(2n^2+2n+3)。这就是大O时间复杂度表示法。大O时间复杂度实际上并不代表代码的具体执行时间，而是表示代码的执行时间随数据规模增长的变化趋势，所以也叫做时间渐进复杂度（asymptotic time complexity），简称时间复杂度。
  • 注意要点
    • 当 n 很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n*n)。

01.关于博客汇总链接

02.关于我的博客