Skip to content

数据结构 & 算法

为什么要学习数据结构和算法?

它对我们开发和程序有什么帮助?

像我们平常都是使用框架和库进行开发的项目的,我们也不太可能去修改库和框架的内部代码,那我们应该如何优化我们的程序,要从哪方面入手呢?可以通过数据处理的操作进行优化,数据处理就会涉及到数据结构和算法的相关内容。

我们的程序一般都是由数据结构和算法结合得到的一个产物(数据结构 + 算法 = 程序),数据结构为算法提供服务,算法围绕数据结构操作。

现实生活举例

数据结构:计算机存储、组织数据的方式,就像生活中的锅碗瓢盆。

算法:一系列解决问题的清晰指令,就像食谱,你做出来的菜好不好吃,取决于你的食谱。在程序里面就代表了,你写出来的程序的性能的优劣。

常见的数据结构

有序数据结构

  • 数组
  • 队列
  • 链表

无序数据结构

  • 集合
  • 字典

树形数据结构

常见的算法

链表

  • 遍历链表
  • 删除链表节点
  • 双指针

树、图

  • 深度优先搜索
  • 广度优先搜索
  • 递归

数组

  • 冒泡排序
  • 选择排序
  • 插入排序
  • 归并排序
  • 快速排序
  • 顺序搜索
  • 二分搜索

常见的算法设计思想

  • 分而治之
  • 动态规划
  • 贪心
  • 回溯

什么是算法?

算法( Algorithm )是指用来操作数据、解决程序问题的一组方法。对于同一个问题,使用不同的算法,也许最终得到的结果是一样的,但在过程中消耗的资源和时间却会有很大的区别。

那么我们应该如何去衡量不同算法之间的优劣呢?

主要还是从算法所占用的「时间」和「空间」两个维度去考量。

  • 时间维度:是指执行当前算法所消耗的时间,我们通常用「时间复杂度」来描述
  • 空间维度:是指执行当前算法需要占用多少内存空间,我们通常用「空间复杂度」来描述

因此,评价一个算法的效率主要是看它的时间复杂度和空间复杂度情况。然而,有的时候时间和空间却又是「鱼和熊掌」,不可兼得的,那么我们就需要从中去取一个平衡点。

可是,我们的代码都还没有运行起来,我怎么能预知到代码运行所消耗的时间和空间呢?由于运行环境和输入规模的影响,代码的绝对执行时间是无法估计的。但是我们却可以预估出代码的基本操作执行次数和额外占用的空间。

接下来会分别介绍一下「时间复杂度」和「空间复杂度」的计算方式。