前言

学了几天的链表,由于我没有具体的学过 C,对指针这一块有时候会很模糊,理解的不透,于是针对数据结构重学了 指针 等预备知识,顺便回顾了 什么是数据结构时间复杂度空间复杂度 等,这些知识还是很重要的,便整理一下发布。

参考了极客时间「数据结构与算法之美」

什么是数据结构?什么是算法?

这俩问题,在我的课本上、百科等地方都有讲述过。但是这些定义很抽象、很拗口,对理解概念感觉没啥实质性的帮助,反而是将这些概念死记住。

从广义上看,数据结构就是指一组数据的存储结构。算法是操作数据的方法。

我们如何把现实中大量而复杂的问题使用特定的数据类型和特定的存储结构保存到主存储器(内存)中,这就是数据结构。接着在此基础上为实现某个功能(比如:增删查改)而执行的操作,叫做算法。

数据结构 = 个体的存储 + 个体间的关系存储
算法 = 对存储数据的操作

学习数据结构与算法,最常用、最基础的如下:

数据结构:数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树。
算法:递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。

复杂度分析

在课本或者其他教程中,开篇除了讲述什么是数据结构和算法外,还有一大重点,就是 时间、空间复杂度。它是衡量一个算法好坏的一大标准。

时间复杂度:程序执行的大概次数,而非执行的时间,因为相同的一个程序在不同型号的测试环境中,测试结果完全不同,例如分别用 i9 处理器和 i3 处理器来运行,那肯定是 i9 的处理速度较快,所以这里不是用时间来衡量。

空间复杂度:算法执行过程中大概所占用的资源(内存)。

时间复杂度

我们在表示一个算法的复杂度时使用大写字母 O,这种表示方法是表示一种变化趋势,通常情况下,把公式中的常量、低阶、系数等忽略,只记录一个最大阶的量级。也就是在分析一个算法、代码的时间复杂度的时候,只关注循环执行次数最多的那一段代码即可

如下代码:

int f(int n) {
    int sum = 0;
    int i = 1;

    for (; i <= n; ++i) {
        sum += i;
    }
    return sum;
}
  • 第 2、3 行代码为常量级的执行时间,对于复杂度没有影响,忽略
  • 进行反复执行的是第 5、6 行代码,这里的代码需要执行 n 次,所以时间复杂度为 $O(n)$

空间复杂度

代码中只申请了一个空间存储变量,例如:int i = 1;,此为常量阶,同样忽略。如果申请的是一个数组,这个数组的长度为 n,那么它的空间复杂度为 $O(n)$。

复杂度分析法则

  1. 单段代码看高频:例如循环
  2. 多段代码取量级最大的:例如有一个单循环和一个嵌套循环,只取嵌套循环的复杂度
  3. 嵌套代码求乘积:例如递归、多重循环
  4. 多个规模求加法:有两个参数控制两个循环的次数,都不确定谁的量级大,这时就取两个复杂度相加

常用的复杂度级别

  • 多项式阶:随着数据规模的增长,算法执行时间和空间按多项式的比例增长。包括:$O(1)$ 常数阶、$O(logn)$ 对数阶、$O(n)$ 线性阶、$O(nlogn)$ 线性对数阶、$O(n^2)$ 平方阶、$O(n^3)$ 立方阶。
  • 非多项式阶:随着数据规模的增长,算法的执行时间和空间占用暴增,此类算法性能极差。包括:$O(2^n)$ 指数阶、$O(n!)$ 阶乘阶。