算法复杂度#

时间复杂度#

衡量算法在输入规模为 $n$ 时所用时间，实际是所作 基本操作（常数时间内可完成且时间与操作数无关） 的次数。

$e.g.$

for(int i = 0; i < len; i++){
	if(arr[i] > max){
		max = arr[i];
	}
}

是 $O(n)$ 的，因为至多进行 $2n$ 次操作。此处 $O$ 可以与数学中 等价无穷大 的概念相类比，运行时间渐进上界。

是 $\Omega(n)$ 的，因为至少进行 $n$ 次操作。此处 $\Omega$ 可以与数学中 等价无穷小 的概念相类比，运行时间渐进下界。

是 $\Theta(n)$ 的，因为操作次数是 $n$ 量级的。此处 $\Theta$ 是运行时间的渐进紧确界。以上三种复杂度中，通常使用渐进上界衡量算法。

• 时间复杂度的计算

首先找出循环最内层的操作，计算操作次数。然后计算其量级，量级较低者直接忽略。

• 各种时间复杂度的典型例子

  1. $O(1)$ 不涉及循环和递归

  2. $O(n)$ 单次遍历

  3. $O(n^{k})$ $k$重嵌套循环，每层执行一定操作，冒泡 / 选择排序

  4. $O(\log{n})$ 注意计算机语境下的对数常以 $2$ 为底，分治 / 二分

  5. $O(n\log{n})$ 部分基于分治的排序算法，归并 / 快排 / 堆排序

  6. $O(k^{n})$ 完全展开递归，枚举集合全部子集

  7. $O(n!)$ 全排列枚举

• 各种时间复杂度的大致规模

空间复杂度#

衡量算法在输入规模为 $n$ 时所占内存空间。

在通常情况下，OJ内存限制在 $256MB$ 上下（包含栈区、堆区、全局/静态存储区），对于32位有符号整型变量，规模约为 $6.7e7$ 量级。

数组回顾#

本质为 线性表 ：每个元素只与前驱、后继相邻。栈、队列、链表也是线性表。

采用 顺序存储 ：数组持有的内存空间是连续的。

$n$ 维数组是 $n-1$ 维数组的数组。数组的存取：首地址+偏移量写入/读取对应地址。

需要区分的是，动态二维数组的内存可以不连续。

• 数组插入/删除元素：扩展/缩减其长度（对于cppvector） ，插入索引后所有元素向后移一位，修改插入位。