算法与数据结构介绍

算法与数据结构介绍

算法和数据结构不受语言限制，每种编程语言都有关于自己的实现

算法

什么是算法

算法是指解题方案的准确而完整的描述，算法是一系列解决问题的清晰指令，算法使用系统的方法来解决问题的机制。

算法作用

对于实际业务（包括底层框架设计，或者实际系统设计）中，针对某些功能实现，不能一直用笨方法来实现，需要一些高级的算法，来对系统功能进行优化，提高系统性能。

例如：对一串数字进行排序，什么场景下适合用什么样的排序最高效，不能一味的循环，这样会导致性能的下降，这样就衍生出了各种排序算法，在合适的情况下使用合适的算法，才是最佳方案。

数据结构

什么是数据结构

数据结构是计算机存储、组织数据的方式。

数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

数据结构反映数据的内部构成，即数据由那部分构成，以什么方式构成，以及数据元素之间呈现的结构。

数据结构就是研究数据的逻辑结构和物理结构以及它们之间相互关系，经过这些运算后所得到的新结构是原来的结构类型。

数据结构主要分两种

线性数据结构=》连续地址

散列数据结构=》非连续地址

数据结构作用

用合适的结构存储数据，压缩空间，是空间利用最大化，数据存储效果最大化。

系统通常的优化方案

在时间和空间上考虑

没有满足空间和时间都节省情况就根据实际要求做

1. 空间换时间
2. 时间换空间

时间复杂度

时间复杂度的意义：衡量算法流程的一种指标，此指标只与数据量有关，与过程之外的优化无关。

时间复杂度计算：时间负责都只关注最高项，不关注其他项与常数项，在样本量很大很大时，会直接影响效率的只有最高阶项，其他（包括常数项，低阶项，每一项的系数）都不重要

O(2N^2 + N + 1)

在当前例子中 N越大，直接影响因素只有 2N^2 同时系数 2 是常量 不起决定因素，所以起决定因素的是N^2 所以时间复杂度为 O(N^2)

额外空间复杂度

实现一个算法必然要开辟一些额外的空间来支持算法的流程

额外空间复杂度计算标注

• 输入参数的空间，不参与计算
• 返回参数的空间，不参与计算

除此之外如果还需要开辟额外的空间来参与计算，那一部分，才是额外空间复杂度

但是如果你开辟的空间进食有限的几个变量，额外空间复杂度也是O(1)

---

时间负责度与空间复杂度的计算会在当前专栏中后续数据结构与算法的介绍中穿插介绍

点个赞呗