数据结构与算法

  • 数据结构是指一组数据的存储结构
  • 算法就是操作数据的方法
  • 数据结构和算法是相辅相成的，数据结构是为算法服务的，而算法要作用在特定的数据结构上

重点

  • 数据结构和算法解决的是如何更省，更快的存储和处理数据，因此需要一个考量效率和资源消耗的方法，这就是复杂度分析方法。
  • 学习数据结构与算法过程中，要学习的的来历，自身特点，适合解决的问题以及实际的应用场景
  • 建立时间，空间复杂度意识，写出高质量代码，设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验，以此获得工作回报，实现价值，完善人生。
  • 大厂考数据结构与算法是因为：相比短期能力，他们更看重你的长期潜力。

为什么需要时间，空间复杂度分析

事后统计：直接跑代码，通过统计、监控得到算法执行的时间和占用的内存大小

  • 测试结果非常依赖测试环境 同样一段代码，分别在i9和i3来运行，i9要快很多。 原本在这台机器上a代码执行速度比b要快，换一台机器，可能结果截然相反
  • 测试结果受数据规模的影响较大 对同一个排序算法，待排序数据的有序度不一样，排序的执行时间就会很大差别。
  • 如果测试数据规模太小，测试结果可能无法真实反应算法性能，对于小规模的数据排序，插入排序可能会比快速排序要快。

大O复杂度表示法

1.大O复杂度表示法:算法的执行效率，粗略的讲就是算法执行时间，实际上是表示代码执行时间随数据规模增长的变化趋势。

2.推倒过程

int cal(int n) {
    int sum = 0; //1次
    int i = 1;  //1次
    int j = 1;  //1次
    for (; i <= n; ++i) { //n次
        j = 1;           //n次
        for (; j <= n; ++j) {//n^2次
            sum += i*j;//n^2次
        }
    }
    return sum;
}

每行代码对应的CPU执行个数，时间都不一样，但是这里只是粗略估计，假定每行代码执行时间都一样，为unit_time。则总的执行时间为 T(n) = (2$n^2$+2n+3)*unit_time，尽管不知道unit_time的具体值，但得出规律：
T(n)与每行代码的执行次数成正比。

结论

T(n)=O(f(n))
  • T(n)代表代码执行的时间，n表示数据规模大小，f(n)表示每行代码执行的次数总和。O表示代码执行时间T(n)与f(n)表达式成正比。
  • 大O时间复杂度实际上并不具体表示代码真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以，也叫渐进式时间复杂度，简称时间复杂度。
  • 例子中的大O表示法为 T(n)=O(2$n^2$+2n+3)，当n很大时，公式中的低阶，常量，系数并不影响增长趋势，所以都可以忽略。只记录一个最大量级就可以了，则例子中最终复杂度未 T(n)=O($n^2$)。
  • 大O时间复杂度实际上并不具体表示代码真正执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所以也叫渐进时间复杂度，简称时间复杂度。

时间复杂度分析

  • 只关注循环执行次数最多的一段代码
int cal(int n) {
    int sum = 0; //1次   常量级，与n大小无关
    int i = 1;  //1次    对复杂度没有影响
    for (; i <= n; ++i) { //n次
        sum += i; //n次
    }
    return sum;
}

T(n)=O(2n),系数忽略,最终，T(n)=O(n)。

  • 加法法则：总复杂度等于量级最大的那段代码的复杂度
int cal(int n) {
    int sum_1 = 0;
    int p = 1;
    //执行了100次，常量级执行时间，跟n的规模无关(当n无限大的时候就可以忽略，时间复杂度的概念是表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量执行时间多大，都可以忽略，本身对增长趋势并没有影响)
    for (; p < 100; ++p) {
        sum_i += p;
    }
    
    int sum_2 = 0;
    int q = 1;
    for (; q < n; ++q) {//O(n)
        sum_2 += q;
    }
    
    int sum_3 = 0;
    int i, j = 1;
    for (; i <= n; ++i) {//O(n^2)
        j = 1;
        for (; j <= n; ++j) {
            sum_3 += i*j;
        }
    }
    
    return sum_1 + sum_2 + sum_3;
}

分别分析每一部分的时间复杂度，再取一个量级最大的作为整段代码的复杂度。则整段代码的时间复杂度是O($n^2$)

T(n)=T1(n)+T2(n)=max(O(f(n)),O(g(n)))=O(max(f(n),g(n)))
T(n)=O(max(f(n),g(n)))=O(max(n,n^2))=O(n^2)
  • 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
int cal(int n) {
    int ret = 0;
    int i = 1;
    for (; i < n; ++i) { //O(n)
        ret += f(i);
    }
}

int f(int n) {  //o(n)
    int sum = 0;
    int i = 1;
    for (; i < n; ++i) {
        sum += i;
    }
    return sum;
}

T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
T(n)=O(f(n)*g(n))=O(n*n)=O(n^2)

常见的时间复杂度实例分析

ccf973f92bf16c863387c2d44694b90a * O(1)

int i,j = 8;
int sum = i + j;

O(1)只是常量级时间复杂度的一种表示方法，并不是只执行了一行代码。这行代码有3行，时间复杂度是O(1)而不是O(3)。只要代码的执行时间不随n的增大而增大，则时间复杂度就是O(1)。

  • O(logn),O(nlogn)
int i = 1;
while (i <= n) {
    i *= 2;//循环次数最多的，计算除这行代码执行了多少次就能算出整段代码的时间复杂度
}

分析: 变量i的值从1开始取，每循环一次乘以2，大于n时结束。 则i的取值为:

$2^0$ $2^1$ $2^2$ $2^3$ … $2^x$=n

只需要知道x的值是多少，就知道这行代码执行次数了。

$2^x$ = n => x = ${log_2{n}}$

结论：O(${log_2{n}}$)

修改一下

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

结论：O(${log_3{n}}$)

最终：不管是以2为底，还是3为底，把所有对数阶的时间复杂度都标记为O($log{n}$)
原因：对数之间可以互相转换。$log_3{n}$=$log_3{2}$*$log_2{n}$,因为$log_3{2}$是一个常量，大O标记复杂度时可以忽略系数，则$log_3{n}$=$log_2{n}$， 所以对数阶时间复杂度表示方法里，忽略对数底，统一表示为O($logn$)。

如果一段代码的时间复杂度是O($log{n}$)，循环执行n次，则时间复杂度就是O(n$log{n}$)了。如归并排序，快速排序。

  • O(m+n),O(m*n)
int cal(int m, int n) {
    int sum_1 = 0;
    int i = 1;
    for (; i < m; ++i) {  //O(m)
        sum_1 += i;
    }
    
    int sum_2 = 0;
    int j = 1;
    for (; j < n; ++i) {  //O(n)
        sum_2 += j;
    }
}

m,n表示数据规模，无法预估，不能用加法规则，时间复杂度为O(m+n)。 如果是乘法规则的一段代码，如2个嵌套，则时间复杂度为O(m*n)

空间复杂度分析

时间复杂度：表示算法执行时间与数据规模的增长关系
空间复杂度：表示算法存储空间与数据规模的增长关系

void print(int n) {
    int i = 0;   //常量阶，跟数据规模n无关，忽略
    int []a = new int[n]; //O(n)
    for (i: i < n; ++i) {
        a[i] = i*i;
    }
    for (i = n-1; i >= 0; --i) {
        print(a[i])
    }
}

只是在第三行申请了一个大小为n的int类型数组，其他代码都没用占用更多空间，所以空间复杂度为O(n)。
常见的空间复杂度O(1),O(n),O($n^2$)，像O(logn),O(nlogn)这样的对数阶复杂度都用不到。

小结

9ab83d88690de341e36a77e796ed35a1

越高阶的复杂度算法，执行效率越低。几乎所有的数据结构和算法的复杂度都跑不出这几个。