数据结构与算法（基础概念）

前言

作为一个非科班出身的代码搬运工，数据结构和算法可以算得上是薄弱的知识领域，在摸索过OC及Swift等底层知识点后，发现苹果底层源码大量运用数据结构方面的知识，想要成为一名“资深”搬运工，掌握数据结构及算法相关的知识是很有必要的。接下来一段时间，我们将一起遨游于数据及算法的海洋中～～～

数据

数据：程序的操作对象，用于描述客观事物。如开发中接口请求到的数据等
数据的特点：可以输入到计算机，可以被计算机处理

数据对象：性质相同的数据元素的集合（类似于数组）
数据元素：组成数据的对象的基本单位 （类似Model）
数据项：一个数据元素由若干个数据项组成 （类似Model中的属性）
它们之间的关系如下图所示：

数据层级关系

结构：数据元素之间不是独立的，存在特定的关系，这些关系即结构。
数据结构：指的是数据对象中的数据元素之间的关系。可分为逻辑结构和物理结构（存储结构）两个分支。
逻辑结构：逻辑结构包括线性结构和非线性结构，线性结构包括线性表、栈和队列、字符串，非线性结构包括集合结构、树结构、图结构。

逻辑结构

物理结构：物理结构包括顺序结构和链式存储结构两种。

物理结构

算法

算法：是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令。在计算机中表现为指令的有限序列，并且每个指令表示一个或多个操作。
设计一个算法需要满足一下5个特点：
1.有穷性：算法的有穷性是指算法必须能在执行有限个步骤之后终止。
2.确切性：算法的每一步骤必须有确切的定义。
3.输入项：一个算法有0个或多个输入，以刻画运算对象的初始情况，所谓0个输入是指算法本身定出了初始条件。
4.输出项：一个算法有一个或多个输出，以反映对输入数据加工后的结果。没有输出的算法是毫无意义的。
5.可行性：算法中执行的任何计算步骤都是可以被分解为基本的可执行的操作步骤，即每个计算步骤都可以在有限时间内完成（也称之为有效性）。

评价标准：可读，正确，健壮，高效，低存储
效率度量：可从时间复杂度和空间复杂度两个方面来度量。

时间复杂度：指执行算法所需要的计算工作量。一般来说，计算机算法是问题规模 n 的 f(n) 函数，算法的时间复杂度也因此记做：

t(n) = o( f(n) )

因此，问题的规模 n 越大，算法执行的时间的增长率与 f(n) 的增长率正相关。
通俗点理解就是执行一段代码，其中每行代码的执行次数之和。

时间复杂度
上图中的O(n)为大O表示法：
1.用常数1取代运行时间中的所有常数，12 -> 1 O(1)
2.在修改运行次数函数中，只保留最高阶项，n³⁺²ⁿ2+5 -> O(n^3)
3.如果最高阶存在且常数不等于1，则去除这个项目相乘的常数，2n^3 -> n^3
注：（以上的各种阶层中，指数阶其实可以不考虑，因为时间消耗过大，实际开发中这种算法能写得出来也不现实。）

空间复杂度：指算法需要消耗的内存空间。其计算和表示方法与时间复杂度类似，一般都用复杂度的渐近性来表示。同时间复杂度相比，空间复杂度的分析要简单得多。
程序空间计算因素：
1.寄存本身的指令
2.常数
3.变量
4.输入
5.对数据进行操作的辅助空间（主要考虑的是辅助空间）

例如数组逆序题，开辟一个临时变量的方法实现的话，空间复杂度就是O(1)，如果是用一个长度为n的数组逆序装进去，再装进原数组中的方法，那空间复杂度就是O(n)。