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

数据结构指一组数据的存储结构
算法就是操作数据的一组方法

关系：数据结构是为算法服务的，算法要作用在特定的数据结构之上。

什么是复杂度分析

  数据结构和算法本身解决的是如何让代码运行的更快，更省存储空间的问题。因此需要从执行时间和占用存储空间两个维度来评估数据结构和算法的性能。分别用时间复杂度和空间复杂度两个概念来描述，二者统称为复杂度。复杂度描述的是算法执行时间（或占用空间）与数据规模增长的关系。

数组

数组是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。

高效的随机访问

因为数组是连续的内存空间和相同类型的数据。造就了它高效的“随机访问”。可以根据寻址公式，可以快速的计算出该元素存储的内存地址。时间复杂度为O(1)。

1
2
3
4
5

// 一维数组的寻址公式，base_address 为内存的首地址，data_type_size 为单个元素的大小
a[i]_address = base_address + i * data_type_size

// 二维数组寻址公式，对于 m * n 的数组
a[i][j]_address = base_address + ( i * n + j) * data_type_size

递归

什么是递归？

1. 递归是一种应用非常广泛、非常高效、简洁的算法（或者编码技巧）。很多数据结构和算法的编程实现都要用到递归，比如 DFS 深度优化搜索、前中后序二叉树遍历等。
2. 方法或函数调用自身的方式称为递归调用，调用称为递，返回称为归。
3. 所有的递归问题都可以用递推公式来表示。（如：f(n) = f(n - 1) + 1 其中 f(1) = 1)

递归的优缺点？

• 优点：递归代码的表达力强，写起来非常简洁。
• 缺点：空间复杂度高、有堆栈溢出的风险、存在重复计算、过多的函数调用会耗时较多。

跳表（SkipList）

对于一个有序链表，要想在其中查找某个值，我们需要从头到尾遍历链表，这样查找效率就会很低，时间复杂度高，是O(n)。为了提高查询效率，我们在链表之上建立多层索引。每隔几个结点向上抽取一层，建立索引层。提高效率。这种链表加多级索引的结构，就是跳表。可以支持快速的插入、删除、查找操作。数据结构如下图所示。