数据结构简述，时间、空间复杂度，学习网站推荐

目录

IT 学习路线

相关坚韧大厚书

相关有趣/耐看书或视频

数据结构与算法学习网站推荐

刷题

时间、空间复杂度

数据结构简述

基本概念

数据结构与算法简述和CS综述整理。本文非基础的教程，本文会列出大量学习和参考网站。老惯例，一个文章是一个集大成（本文借助了语音输入（PC 版 讯飞输入法）由此加速码字，但仍保持简洁的文风）。

数据结构 + 算法 = 程序。数据结构：现实问题的符合计算机存储的建模；算法：解决现实问题的步骤（符合有穷性，确定性，可行性等）。

IT 学习路线

1. C语言基础（看书、B站等均可） →

2. C语言三剑客：《C和指针》、《C陷阱与缺陷》和《C专家编程》，经典永流传 →

3. 数据结构与算法（线性表/树/图/哈希 + 排序/搜索/规划等等等 按需学） →

4. 计算机专业学科看。《计算机组成原理》/《计算机体系结构》；《计算机操作系统》/《现代操作系统》/《深入理解计算机系统》；可选《编译原理》、《深入分析GCC》；网络协议如《计算机网络》、《TCP-IP详解卷一/卷二/卷三》等 →

5. 可选 《CPU自制入门》 →

6. 走向：嵌入式 Linux 方向、FPGA / 芯片设计 / 验证方向、具体某算法方向（如 CV、ML、DL）等等。

更多可详细参考 rd2coding/Road2Coding: 编程之路 (github.com) 的总结，比较全面了。

相关坚韧大厚书

没给出链接的 网搜名字即可。

• 哪本《数据结构与算法》最好？ - 知乎 (zhihu.com) 该回答列举了一些不错的数据结构与算法方面的书籍。

• 《算法导论》（经典）是计算机学科的算法入门书。

• 《计算机体系结构》（经典），《计算机操作系统》/《现代操作系统》/《深入理解计算机系统》。

• 《编码的奥秘》，相关介绍/推荐 想练习《编码的奥秘》里面的知识，有什么软件有帮助？ - 知乎 (zhihu.com)。《编译原理》（经典），《深入分析GCC》。

• 网络协议如《计算机网络》、《TCP-IP详解卷一/卷二/卷三》， 想深入了解 HTTP 协议，有哪些值得推荐的书籍？ - 知乎 (zhihu.com)。

• 嵌入式应用相关：《GNU Make》，《Debugging with GDB》，《Linux 高级程序开发》，《POSIX 多线程程序设计》，《嵌入式Linux基础教程》，《嵌入式Linxu应用开发完全手册》，《嵌入式Linxu应用程序开发详解》。

• 嵌入式底层相关：内核相关：《深入理解Linux内核》，《Linux内核源代码情景分析》，《Linux内核设计与实现》；驱动相关：《Linux设备驱动程序》，《Linux设备驱动开发详解》，《Linux驱动开发入门与实践》。

相关有趣/耐看书或视频

• 学习心得介绍 | 小林coding (xiaolincoding.com)。介绍 | 小林coding (xiaolincoding.com)。

• 13 万字 C 语言从入门到精通保姆级教程2021 年版_极客江南的博客-CSDN博客。

• tangtangcoding/C-CppLearning: C语言与C++学习 (github.com)，内容超多。

• 图解系统 小林，笔记：图解系统（小林coding）_NiXGo的博客-CSDN博客，推荐。

• 图解网络 小林，推荐。

• 趣谈网络协议。

• 手绘图解 HTTP。30张图解HTTP常见面试题。

• TCP/IP 教程 | 菜鸟教程 (runoob.com)。HTTP 教程 | 菜鸟教程 (runoob.com)。

• 《嵌入式C语言的自我修养》 从沙子讲到 CPU，从编辑器讲到编译器，从高阶 C 语言讲到内存管理，从 GNU 讲到多任务编程。

• （完结）（小甲鱼）数据结构和算法_ 哔哩哔哩 _bilibili。

• 国嵌唐老师主讲【数据结构与算法C语言】（非常犀利）_ 哔哩哔哩 _bilibili 讲的慢。

• 《算法新解》开源书，我为什么加下划线？，《啊哈！算法》。

数据结构与算法学习网站推荐

• 代码随想录 (programmercarl.com)，推荐，一站式，比较全。

• 数据结构部分简介 - OI Wiki (oi-wiki.org)。

• SummerLife/DataStructure: 记录学习浙江大学《数据结构》课程的学习笔记和练习题， 以及在工作中常见数据结构的整理 (github.com).

• 算法入门教程（多语言实现） (biancheng.net)。

• 算法基础简介 - OI Wiki (oi-wiki.org)。动态规划部分简介 - OI Wiki (oi-wiki.org)。

• 字符串部分简介 - OI Wiki (oi-wiki.org)。

• 图论部分简介 - OI Wiki (oi-wiki.org)。

• 编程干货：15 个最有用的数据结构和 15 个最重要的算法_机器人技术与设计-面包板社区 (eet-china.com)。30 个重要数据结构和算法完整介绍(建议收藏保存)-云社区-华为云 (huaweicloud.com)。

刷题

• 花了几千大洋买的200集算法面试突击课程，现在面试成功全部免费分享给大家哔哩哔哩bilibili。

• LeetCode 最热门 100 题哔哩哔哩bilibili。

• 本文文末附录：附：算法刷题总结。

时间、空间复杂度

时间复杂度表示一个算法内执行语句的数量在最坏的情况下随着循环次数 n 的增加而增长的数量级。一个算法内语句的使用次数（频度）表示为 f(n)，n 为算法内循环语句的循环数，n 的变化直接改变 整个算法的语句使用次数；时间复杂度 O(g(n)) 的定义为，对于一个算法，当且仅当存在正整数 c 和 n0，使得 f(n) ≤ cg(n) 对于所有 n ≥ n0 成立，则该算法的渐进时间复杂度为 f(n) = O(g(n))，g(n) 为 n 的函数。

各个时间复杂度的语句频度的增长速度比较：O(log_2(n)) ＜ O(n) ＜ O(n*log_2(n)) ＜ O(n^2) ＜ O(n^3) ＜ O(2^n) ＜ O(n!)，前三个很好，最后两个不可接受，剩余的强差人意。

程序的执行时间不仅依赖于问题规模，还可能随着数据的状态不同而变化，即其时间复杂度会变化，一般评价算法时候取最坏的情况的时间复杂度。

空间复杂度大同小异。

数据结构简述

一个软件项目，数据结构设计的好，后面进行功能实现时候的调用、修改和查询会特别方便，可以达到事半功倍的效果。

基本概念

数据结构几大类

• 线性表：

  • 顺序（数组），

  • 链式（链表（单链表、双向链表、循环链表（单向、双向），静态链表（借助数组实现））），

  • 特殊（栈（FILO）、队列/堆（FIFO））。

• 树：二叉树、红黑树等。

• 图：无向图、有向图等。

• 索引/散列：Maps、Hash Table。

按照关系划分

• 按照逻辑关系（元素的连接关系）：

  集合，线性（数组、栈、队列/堆、链表等），树状（一对多），图状（多对多）。

• 按照存储关系：

  • 顺序存储：如数组，要提前申请空间（静态分配（编译时进行）或动态分配（malloc & free））。优点：物理位置连续而紧凑，可 随机 / 直接 存取；缺点：会产生内存碎片，增、删改动时前后要跟着变（需要移动大量元素）。

  • 链式存储：如链表、树、图，要提前申请空间（动态分配（malloc & free））。优点：链式、离散、节点化，空间可动态分配，改动方便（改节点的指向）；缺点：空间占用大，查找不便（需要遍历整个链表）。

  • 索引存储：“索引-数据”（Key-Value，也叫 Maps） 的结构形式。Java、C++ 中为“map，Python 中为 dictionary。

  • 散列存储：如哈希表（Hash Table）等。

数据运算

• 每个基本数据结构要实现的基本操作：增（插入）、删（删除）、改（更新）、查（检索），判（判空，判满）、排（排序）、复（复位）。

• 更复杂的操作可用以上基本操作实现。

操作的时间复杂度

具体概念在 “C & MCU编写规范和其他” 一文的 “时间、空间复杂度” 一节有提到。（数据结构）十分钟搞定时间复杂度（算法的时间复杂度） - 简书 (jianshu.com)。一套图 搞懂“时间复杂度”_ 12 26 25 的博客-CSDN博客 _时间复杂度。

• 查找：顺序存储结构 O(1)，单链表 O(n)。

• 插入和删除：顺序存储结构 O(n)，单链表 O(1)。