数据结构与算法系列二(复杂度分析)

waitwolf 2020-02-21

1.引子

1.1.为什么要学习数据结构与算法?

有人说,数据结构与算法,计算机网络,与操作系统都一样,脱离日常开发,除了面试这辈子可能都用不到呀!

有人说,我是做业务开发的,只要熟练API,熟练框架,熟练各种中间件,写的代码不也能“飞”起来吗?

于是问题来了:为什么还要学习数据结构与算法呢?

#理由一:
    面试的时候,千万不要被数据结构与算法拖了后腿
#理由二:
    你真的愿意做一辈子CRUD Boy吗
#理由三:
    不想写出开源框架,中间件的工程师,不是好厨子

1.2.如何系统化学习数据结构与算法?

我想好了,还是需要学习数据结构与算法。但是我有两个困惑:

1.如何着手学习呢?

2.有哪些内容要学习呢?

学习方法推荐:

#学习方法
1.从基础开始,系统化学习
2.多动手,每一种数据结构与算法,都自己用代码实现出来
3.思路更重要:理解实现思想,不要背代码
4.与日常开发结合,对应应用场景

学习内容推荐:

数据结构与算法内容比较多,我们本着实用原则,学习经典的、常用的数据结构、与常用算法

#学习内容:
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
    数组、链表、栈、队列
    散列表、二叉树、堆
    跳表、图
5.常用算法
    递归、排序、二分查找
    搜索、哈希、贪心、分治
    动态规划、字符串匹配

2.考考你

在开篇中提到了复杂度分析,与大O表示法的概念。具体要如何进行复杂度分析,以及大O表示法的公式推导,我们在这一篇详细来看。

#考考你:
1.你知道大O表示法,公式是如何来的吗?
2.你知道时间复杂度分析的常用原则吗?
3.你知道常见复杂度的度量级吗?

3.案例

3.1.大O表示法公式推导

3.1.1.案例代码

我们根据以下案例代码推导大O表示法的公式。代码很简单,有没有?

// 传入参数n,求解1..n的累加和
public int sum(int n){
    int sum = 0;
    for(int i = 1; i <= n; i++){
        sum += i;
    }
    
    return sum;
}

3.1.2.推导过程

简述:

1.对于程序代码中的每一行代码,从cpu的角度来看,执行的时候都有:读数据->运算->写数据过程

2.我们假定每一行代码的执行时间都相同,都是一个单位时间:unit_time

3.那么sum方法中,代码执行的总时间是多少呢

public int sum(int n){
   int sum = 0;// 第二行代码执行,需要1 个unit_time
   for(int i = 1; i <= n; i++){// 第三行代码执行,需要n 个unit_time
       sum += i;// 第四行代码执行,需要n 个unit_time
   }   
   return sum;// 第五行、第六行代码暂时忽略,不影响
}

4.根据3推导,sum方法的总执行时间是:

T(n)=(n + n + 1) * unit_time = (2n +1) * unit_time=O(f(n))

5.结论:所有代码的执行时间T(n),与每行代码的执行次数成正比

6.提取出公式即:T(n) = O(f(n))

#公式解读:
 T(n):代表代码执行时间
 n:代表数据规模
 f(n):代表每行代码执行的次数总和
 O:表示代码执行时间T(n),与代码执行次数f(n)成正比

7.这就是大O表示法的公式来源,表示代码的执行时间T(n),与代码的执行次数f(n)成正比

8.进一步理解:

1.大O表示法:时间复杂度,表示数据规模n的增长,与算法执行时间的增长趋势
2.大O表示法:空间复杂度,表示数据规模n的增长,与算法存储空间的增长趋势

3.1.3.约定

大O表示的公式,以及含义我们已经推导出来了。它表示的是数据规模n的增长,与算法执行时间,或者存储空间的增长趋势。这里需要关注两个字:趋势

根据常理我们知道,常量系数低阶不会影响趋势,因此在实际复杂度分析中,往往忽略常量、系数、低阶。

那么上面案例的时间复杂度大O表示法公式,省略系数、常量:

可以从:T(n) = O(f(n)) = O(2n+1)

简化成:T(n) = O(n)

3.2.时间复杂度案例

在复杂度分析中,有时间复杂度分析和空间复杂度分析。它们是从两个维度来衡量算法的优劣。实际分析方式类似,我们以时间复杂度分析为例。

时间复杂度分析,有几个基本的原则,你都知道吗?

#时间复杂度分析基本原则
1.只关注循环次数最多的代码
2.加法法则:总复杂度等于量级最大的那段代码的复杂度
3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

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

案例代码:

public int sum(int n){
   int sum = 0;// 第二行代码执行,需要1 个unit_time
   for(int i = 1; i <= n; i++){// 第三行代码执行,需要n 个unit_time
       sum += i;// 第四行代码执行,需要n 个unit_time
   }   
   return sum;// 第五行、第六行代码暂时忽略,不影响
}

复杂度分析:

1.这里的原则:只关注循环次数最多的代码

2.第二行代码执行,需要1 个unit_time

3.第三行代码执行,需要n 个unit_time

4.第四行代码执行,需要n 个unit_time

5.第五行、第六行代码暂时忽略,不影响

6.通过以上分析,第三行、第四行代码循环执行次数最多:n。因此时间复杂度为:O(n)

3.2.2.加法法则

简述:

加法法则:总复杂度等于量级最大的那段代码的复杂度

案例代码:

public int sum(int n){
    
    // 第一段代码
    int sum_1 = 0;
    for(int i=1; i< 100; i++){
        sum_1 += i;
    }
    
    // 第二段代码
    int sum_2 = 0;
    for(int j = 1; j <= n; j++){
        sum_2 += j;
    }
    
    // 第三段代码
    int sum_3 = 0;
    for(int k = 1; k <= n;k++){
        for(int h = 1; h <= n; h++){
            sum_3 += k * h
        }
    }
    
    return sum_1 + sum_2 + sum_3;
    
}

复杂度分析:

1.在sum方法中有两段代码

2.第一段代码,复杂度是:O(100)

3.第二段代码,复杂度是:O(n)

4.第三段代码,复杂度是:O(n^2)

5.总复杂度是:O(100) + O(n) +O(n^2)

6.根据加法法则,最终复杂度是:O(n^2)

3.2.3.乘法法则

简述:

乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

案例代码:

public int sum(int n){
     int sum_1 = 0;
    for(int i=1; i< n; i++){// 第一层循环
        sum_1 += multi(i) ;// multi方法中,有第二层循环
    }
}

public int multi(int n){
    int multi_1 = 0;
    for(int i = 1; i<= n; i++){// 第二层循环
        multi_1 *= i;
    }
    
    return multi_1;
}

复杂度分析:

1.在sum方法中,有第一层循环:for(int i=1; i< n; i++){

2.在sum方法中,调用multi方法

3.在multi方法中,有第二层循环:for(int i = 1; i<= n; i++){

4.根据乘法法则,总时间复杂度等于,第一层循环,乘以第二层循环

5.因此总时间复杂度是:O(n*n) = O(n^2)

4.讨论分享

#考考你答案:
1.你知道大O表示法,公式是如何来的吗?
 1.1.参考【3.1.大O表示法公式推导】
 
2.你知道时间复杂度分析的常用原则吗?
 2.1.只关注循环次数最多的代码
 2.2.加法法则:总复杂度等于量级最大的那段代码的复杂度
 2.3.乘法法则:嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
 
3.你知道常见复杂度的度量级吗?
 3.1.常数阶:O(1)
 2.2.对数阶:O(logn)
 2.3.线性阶:O(n)
 2.4.线性对数阶:O(nlogn)
 2.5.平方阶:O(n^2)
 2.6.立方阶:O(n^3)

相关推荐