数据结构与算法之美

大 O 时间复杂度表示法: T(n)=O(f(n))

n 表示数据规模， T(n) 表示代码运行的耗时， f(n) 表示每行代码执行次数的总和，是一个公式， O 代表 T(n) 和 f(n) 成正比。 大 O 时间复杂度表示代码随规模增长的变化趋势，并不是真正的执行时间，所以叫 渐进时间复杂度（asymptotic time complexity） ，简称 时间复杂度 。

分析方法：

• 只关注循环次数最多的一段代码
• 加法法则：总复杂度等于量级最大的那段代码的复杂度
• 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积

常见时间复杂度分析：

其中 O(\({2^n}\)) 和 O(n!) 为非多项式量级，其他为多项式量级。非多项式量级算法会随着规模 n 的增大，执行时间急剧增加，是非常低效的算法，我们主要 关注 多项式时间复杂度 ：

• O(1)

  只要代码执行时间不随着 n 的增大而增长，时间复杂度即为 O(1) ，如果代码中不含有循环、递归等类型代码，成千上万行代码的时间复杂度也是 O(1)

• O(logn)、O(nlogn)

  i = 1
  while i < n:
      i = i * 2
  

上面这个循环代码执行次数可以通过 2^x=n , 求得 x=log₂n ，则时间复杂度为 O(log₂n) ,如果换成 i * 3 ，那么时间复杂度为 O(log₃n) , 因为对数之间是可以相互转换的，所以可以忽略对数的“底”，统一表示为 O(logn)。O(nlogn) 自然就是循环嵌套了，O(nlogn) 也是一种比较常见的算法时间复杂度， 如归并排序、快速排序的时间复杂度都是 O(nlogn)。

• O(m+n)、O(m*n)

此类时间复杂度是由两个数据的规模决定的

def cal(m, n):
    i = j = 1
    sum1 = sum2 = 0

    while(i < m):
	sum1 += i
	i++

    while(j < n):
	sum2 += j
	j++
    return sum1 + sum2

我们无法估计 m 和 n 的量级谁大，就不能简单地使用加法规则，忽略掉其中一个，所以算法复杂度为 O(m+n)，如果是嵌套的，则乘法规则依然有效即时间复杂 度为 O(m*n)。

空间复杂度全称 渐进空间复杂度(asymptotic space complexity) ，表示算法的存储空间和数据规模之间的增长关系。

可以粗略的估计，越高阶复杂度的算法，执行效率越低。 常见的复杂度从低阶到高阶： O(1)、O(logn)、O(n)、O(nlogn)、O(n²)

• 最好情况时间复杂度（best case time complexity） : 就是在最理想的情况下，执行代码的时间复杂度。
• 最坏情况时间复杂度（worst case time complexity） : 就是在最糟糕的情况下，执行代码的时间复杂度。
• 平均情况时间复杂度 : 全称应该叫做 加权平均时间复杂度 或者 *期望时间复杂度*。
• 均摊时间复杂度 ： 对一组数据结构连续操作时，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，这些操作时间存在前后的时序关系，

这个时候可以尝试使用 摊还分析 （平摊分析），看能否将较高时间复杂度的耗时平摊到时间复杂度较低的操作上； *一般是可以使用均摊复杂度分析的场合，均摊时间复杂度=最好情况时间复杂度*。

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

定义中的几个概念：

• 线性表：数据排列像“线”一样的结构，只有前后两个方向，如数组、栈、队列、链表等

• 非线性表: 数据之间不是简单的前后关系，如：树、堆、图等

• 连续的存储空间和相同的数据类型：正是因为这两点，数组才具备了“杀手锏”的特性：随机访问。

以长度为10的数组为例 int[] a = new int[10] ，内存块的首地址为 base_address=1000

计算机会给每个内存单元分配地址，通过地址来访问内存中的数据，寻址公式： a[i]_address = base_address + i * data_type_size 。

数组适合查找操作，但时间复杂度不是 O(1)，即使是排好序的数据，使用二分查找，时间复杂度也是 O(logn)，所以，准确的表述应该是： *数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)*。

数组的插入和删除，最好情况时间复杂度为 O(1) 即从末尾插入或删除元素；最坏时间复杂度为 O(n) 即从开头插入或删除元素，平均时间复杂度为 O(n)， 所以 a[k]_address = base_address + k * type_size ，而如果数组从 1 开始，那么 a[k]_address = base_address + (k-1) * type_size 有大量的搬移操作。

从数组的存储模型上来看，“下标”最确切的定义应该是“偏移(offset)”， a[0] 就是偏移为 0 的位置，a[k] 表示偏移 k 个 type_size， 所以 =a[k]_address = base_address + k * type_size ，而如果数组从 1 开始，那么 a[k]_address = base_address + (k-1) * type_size ， 每次随机访问数组，多了一次减法运算，对 cpu 来说就多了一次减法指令，数组作为基础的数据结构，随机访问又是基础操作，所以效率的优化需要 做到极致。当然也有可能是 C 语言使用 0 作为数组下标的开始，其他语言纷纷效仿。

数据分配的存储空间需要是连续的，而链表则不需要连续。

我们可以维护一个有序的单链表，越早访问的节点越靠近尾部。

当有一个新数据访问时，遍历单链表，

如果命中，把对应节点从原位置中删除，再重新插入到链表头部。

如果没有命中，将节点插入到链表头部，需要区分两种情况：

• 链表已满，需要删除最后一个节点，并将新节点插入到头部
• 链表未满，直接将新节点插入到头部

无论链表满没满，都需要遍历链表，所以时间复杂度为 O(n)。