数据结构与算法

Posted on In , Views: Waline:

Algorithms + Data Structures = Programs
编程的核心是数据结构，而非算法，好的数据结构是好算法的基础。
选择合理的数据结构，并将一切组织有序，正确的算法也就显然了。

Intro to Data Structures and Algorithms - Udacity
Data Structures and Algorithms - Coursera
The Complete Guide to Google Interview Preparation
动态规划 https://www.bilibili.com/video/av29915579
https://the-algorithms.com/

Data Structure

广义的数据结构可分为原始数据结构及原始数据所组成的复杂结构。前者对应于基本数据类型，如整型、浮点型、字符、布尔、指针等；后者则对应通常意义上的数据结构，即原始数据类型的组织结构，在Python通常被称为容器类型(Container)，如字符串、列表、数组、元组、字典、集合等。

数据的组织结构大致可分为线性与非线性两类，前者如常见的数组、列表、链表、队列、堆栈等，后者如树以及图。而在逻辑上的组织结构之外，实际的存储实现上又有不同，有顺序、链式、索引及散列四种方式。逻辑上的线性结构实际存储可以是散乱的，如链表；而同一图结构可以存储为邻接矩阵、邻接表、边集数组等不同形式。

Structure

Logical:

Organization Topology Examples Comments
Set Set, Dict 一堆互不关联的条目
Linear Array/List, Linked List,
Stack, Queue		 一维顺序排布
Grid (2D)Matrix/DataFrame,
nD-Array		 二维或多维网格排布
Hierarchical Binary Tree, Trie, Heap 一对多关联的层级网络
Network Graph: weighted, cyclic,
directed, undirected, mixed
connected, unconnected,
simple graph, multigraph		 多对多关联的一般网络

Storage:
数据结构的最终目的是实现数据的存储、访问及各种操作运算，上面介绍的拓扑结构在一定程度上决定了数据访问和操作的逻辑顺序，但其最终实现则依赖于数据的物理存储(硬盘或内存)。数据的存储结构可能和其逻辑结构直观上有很大区别：比如逻辑上的线性链表，实际存储位置可以是散乱的(链式)；而逻辑上非线性的堆，又可以由顺序存储的数组来实现。而且同一数据结构也可由多种存储结构实现：比如网络图结构就存在邻接数组、边值数组以及邻接表等不同存储实现。数据存储结构一般分顺序(Sequential)、链式(Linked)、索引(Indexed)及散列(Hashed)四种方式。如果将散列也视为一种索引则只有三类，且索引(含散列)存储的最终实现也建立在前两者之上。

  • 顺序存储：要求逻辑上相邻的元素存储单元也相邻，由单元相对位置表示逻辑关系
    • 只需要数据头地址和数据相对头的位置(以及每个单元占据的存储空间大小)便可计算出存储地址，实现快速的随机访问
    • 无需额外空间存储节点间的逻辑关系，存储密度高，但插入或删除元素时，需要移动后续所有元素，以保持逻辑关系，不适合处理频繁增删的数据
    • 必须占用相邻的整块存储单元，容易产生较多的存储碎片(硬盘或内存)
  • 链式存储：不要求逻辑上相邻的元素在物理位置上也相邻，借助指针记录逻辑关系
    • 必须沿着数据的指针依次访问，直到找到所需数据，无法实现随机访问
    • 需要额外空间存储指针信息，但插入和删除元素时，只需修改指针指向
    • 无需预分配整块的连续存储单元，可更加灵活和充分的利用存储空间
  • 索引存储：将数据的逻辑结构从数据中剥离出来，在数据之外单独建立附加的索引
    • 不同于顺序或链式存储，索引存储中数据的逻辑结构由单独的索引记录
    • 数据本身由顺序或链式存储实现，索引同样需基于顺序或链式存储实现
    • 由于存储与逻辑去耦，对同一组数组的不同关键字可以建立不同的索引
    • 附加的索引需要占用额外存储，但相应的有助于提升数据访问速度

所谓索引，就是一种可以通过关键字快速定位数据(存储地址)的结构，如字典目录。索引记录了关键字与数据地址间的对应关系，并通过特定结构实现数据的快速查找(及增删)。最常见就是搜索树和散列表，前者基于有序的树结构实现关键字的快速查找，后者则借助散列函数由关键字直接计算出存储地址。散列存储只依赖于散列函数，因此检索、增删操作都很快，而搜索树需要随着数据增删同步更新；但相对的，如果散列函数选择不好，则易出现散列冲突，增加时间和空间开销。此外，散列索引只能用于数据的精确定位(等于)，而无法处理数据的范围索引(大于/小于)。具体应用上，Python字典/集合底层实现为散列表，而搜索树索引(如B+树)多用于硬盘文件系统及数据库等数据量较大的情况。

好的索引设计能极大提升数据的检索效率，汉语字典就有拼音、部首(+笔画)及现在不太常见的四角号码等多种索引方式。拼音或部首索引都需要(按字母或笔画)排好序用于查表，以实现定位；四角号码则是根据字形直接得出编码进行定位。这里前者对应搜索树(有序树结构)，后者则对应散列表。用拼音要知道读音，用部首要知道部首及笔画，四角号码则由字形及相应的规则直接得出编码，尤其适合处理生僻字。不过四角号码索引也存在“散列冲突”问题：使用四位数字编码时会存在较多重码，于是引入一位补码，虽并未完全解决问题，但很大程度上缓解了问题。最后，现实中一些字典虽然提供四角号码索引，但主体依然是按拼音顺序排版，这种情况下四角号码并不能直接实现定位，依然需要查表。只有按四角号码顺序排版的字典，才可根据字形，由四角号码直接实现定位。

不同的存储方式在查找、插入、删除等基本操作上互有优劣，顺序存储和链式存储位于两个极端：前者存储密度高、寻址容易，但插入删除代价高；后者则寻址复杂度高，插入删除简单。而索引存储则居于两者之间，可以实现相对快速的查找，也可以较灵活的插入删除，但需要维护额外的索引(或选择合适的散列函数)。同一数据结构在实现时可以基于不同存储结构，比如前面提到过图结构就有邻接数组、边值数组及邻接表等不同实现，又比如队列和栈可以由数组实现是(顺序存储)，也可以由链表实现(链式存储)。最终具体的选择，需要在实现算法时，根据实际需求确定。

Examples

Linear:

DataStruct Illustration Comments
Array 存储在连续的内存/硬盘空间中，典型的顺序存储
Linked List 存储在先后串联的一系列节点中，典型的链式存储
常见变种有循环链表、双向链表等
Stack /
Queue		 后进先出(LIFO) v.s. 先进先出(FIFO)
实现上可基于数组(速度快)，也可基于链表(无限容量)
Deque 双端队列(double-ended queue, deque)，两端都可出入的队列，即可作为队列，也可用作栈。

Non-Linear:

DataStruct Illustration Comments
Tree 根据不同特征判据，树可分二叉、三叉、四叉…；平衡、偏斜；有序、无序等。
搜索树是最常见的树，其主要优势在于快速检索，而为此搜索树必须是有序树。
根据具体的应用，其他常见的树结构有堆(Heap)、字典树/前缀树(Trie)、后缀树(Suffix Trie)等。
Threaded
Binary Tree
(In-order)		 线索二叉树就是在普通二叉树基础上添加便于按特定顺序遍历树的指针(“线索”)。
最常见的是中序线索二叉树，可利用普通二叉树中的空余指针来提供线索。
B+Tree B+树属于多路搜索树，且不同于普通B树(B-树, 多路的平衡树)，非叶子节点仅存储键值，不存数据。
数据存储叶节点(位于同一层)；叶节点键值按照大小顺序排列，并组成链表；数据页之间会通过双向链表连接。
B+树通常子节点数多(≳100)，层数少，检索效率高，主要用于块存储数据的检索，如文件系统、数据库等。
Graph 图数据最简单的存储方式是邻接矩阵：将顶点存于一维数组、对应的边值(权重)存为二维数组，其缺点为占用空间，且增删顶点复杂度高。
其他常见存储方式有：邻接表/逆邻接表、十字链表(有向图)、邻接多重表(无向图)。(逆)邻接表法将顶点存储于数组，并指向存储关联顶点的链表，占用空间少，但相对的难以判断顶点间是否有边，顶点出入度不可兼得，十字链表及邻接多重表是分别针对有向图和无向图所做的优化。
最后，除了以顶点数组为出发点，还可以边为出发点，建立边集数组，记录每条边的起点、终点、权值。
Hash Table 通过散列函数将关键字直接映射到表中的地址，实现快速检索。
散列函数有多种选择，简单的有取余、折叠、平方取中、伪随机等，字符串可对其字符ASCII码值进行操作，高级的有MD5、SHA1、SHA256等。
出现碰撞时可以使用链表或再散列处理，也可建立公共溢出区。

Python

Python常见内置容器类型的官方(CPython)实现：

  • 基于数组实现：
    • 列表list：可变数组，元素为指针(指向列表内容)
    • 元组tuple：不可变数组，元素为指针(指向元组内容)
    • 字符串str：不可变数组，元素为Unicode字符
    • 字节串bytes：不可变数组，元素为字节码(8位二进制，0-256的整数)
    • 字节数组bytearray：可变数组，元素为字节码(8位二进制，0-256的整数)
    • 数组array.array：可变数组，元素为字符('b','u')或数值('i','l', 'f', 'd')
  • 基于散列表实现：
    • 字典dict：散列表，Python 3.7+中会使用额外的索引表保持字典顺序
    • 集合set：散列表(只保留键，值为空的字典)
    • 不可变集合frozenset：不可变散列表
    • 计数类collections.Counter：字典，键为元素，值为计数
    • 默认值字典collections.defaultdict：字典，由指定函数设置初始取值
  • 其他数据类型：
    • 双端队列collections.deque(double-ended queue)：双向链表
    • 堆队列heapq(heap queue)：类似列表
    • 优先队列queue.PriorityQueue：基于heapq
    • 有序列表bisect.bisect：有序列表的二分查找/插入
    • 枚举类型enum：
    • 命名元组collections.namedtuple：内部实现为类对象，内存使用上有优化

注1：理论上，可变数组长度变化(增删元素)时，应重新分配空间并复制所有数据；实际上，为避免频繁执行复制操作，通常会在实际所需空间之外自动分配冗余内存(如2倍于所需空间)，只有当空间占用比例过高或过低时，才会重新分配空间并复制所有数据。CPython实现中over-allocates会以4的整数倍进行分配：(n + n/8 + 6)//4×4
注2：散列表为避免hash碰撞，通常也需要额外分配大量冗余空间。

Algorithm

根据分析的具体角度，算法可以有多种不同分类方式ref：

  • 数据结构：整数/数论、字符串、图算法/图论、树算法…
  • 应对问题：排序、查找、编码、最优化、数值分析、统计学习、计算几何…
  • 实现方式：递归、循环；串行、并发、并行、分布式；在线、离线；经典、量子…
  • 思想策略：暴力、递归、减治/分治、变治、贪心、动态规划、回溯、随机、近似…
  • 复杂度：常数阶、对数阶、线性阶、线性对数阶、多项式阶、指数阶、阶乘…

Common Tasks

  • 排序: Insertion Sort, Selection Sort; Mergesort, Heapsort, Quicksort, Shell Sort; introsort, Timsort; Bubble Sort; Counting Sort, Bucket Sort, Radix Sort…
  • 查找：Linear search, Jump ~, Binary ~, Exponential ~, Interpolation ~, Fibonacci ~; [选择/kth order statistic]Quickselect, Introselect; [树/图]广度优先(BFS)/逐层遍历、深度优先(DFS: preorder, inorder, postorder)
  • 图：[遍历]广度优先, 深度优先, 最佳优先, 回溯, 集束, 分支定界、最短路(Dijkstra, A*, Floyd-Warshall, Bellman-Ford)、最小生成树(Prim, Kruskal)、旅行商问题(TSP); [网络流] 最大流、运输问题、分配/匹配、环路检测(Floyd)、拓扑排序(Kahn)、着色
  • 数组/字符串：排序、查找/选择(kth order)、翻转、移位、排列组合、[子序列匹配/查找] 众数/字符(Boyer–Moore)、最大和(Kadane)、最长递增、最长公共、最长无重复、最长回文(Manachar)、匹配(KMP, Boyer–Moore)、通配符、正则表达式
  • 数论算法：素数查找、最大公约数(辗转相除)、最小公倍数、同余模、进制位
  • 数值分析：求根(牛顿法)、线性代数(SVD)、数值优化(GD)、微积分、FFT、模拟MC
  • 最优化：[规划]线性~(单纯形), 整数~(割平面, 分支定界)、凸优化(内部点, 椭球)、数值优化、近似/启发式(演化算法、遗传算法、模拟退火、禁忌搜索)
  • 编码通信：压缩/解压(Huffman, LZ77)、哈希、加密/解密(DES, AES, RSA, ECC)、纠错
  • 统计学习：机器学习(SVM,EM)、深度学习(CNN, RNN)、强化学习(Q-Learning)
  • 计算几何：定位、导航、平面扫描、光线追踪
  • 其他(Misc.)：操作系统、数据库、网络、分布式系统、控制论…

Strategies

算法的基本思想或者说解决问题的基本思路，专业说法为算法范式(Algorithmic Paradigm)或算法设计范式(Algorithm Design Paradigm)，通常只在算法设计类书籍中才会专门讨论。思想可以指导实践，但了解了这些思想并不意味着就掌握了算法，相反这些思想需要在针对实际问题的具体算法实现中去融会贯通，所以很多算法类书籍，如算法导论，都是将编程思想穿插在针对具体问题或数据结构的算法中，而不是单独讨论。
Do We Teach the Right Algorithm Design Techniques?

  • 暴力(Brute Force)/穷举：Selection Sort, Linear Search
  • 递归(Recursive)：Fake it 'til you make it
  • 分治(Divide and Conquer)：Quicksort, Mergesort, Binary Search, FFT
  • 减治(Decrease and Conquer)：Insertion Sort, Prune and Search
  • 变治(Transform and Conquer): Heapsort, Presorting, Hashing, Kernelization
  • 贪心(Greedy Algorithm): Huffman Coding, Dijkstra, Prim, Kruskal
  • 动态规划(Dynamic Programing)： Bellman–Ford, Floyd–Warshall
  • 状态树搜索(State Space Tree)：Backtracking/Trial-and-error, Branch and Bound
  • 随机化(Randomized)：Quicksort, Monte Carlo, Las Vegas, Sherwood
  • 启发式(Heuristic)/近似：Simulated Annealing, Tabu Search, A* search
  • 模拟(Simulated)：Simulated Annealing, Random Process, Markov chain

大部分思想的名称都已直观反映了其核心策略，这里简单做一些补充说明：
递归：基础是将问题分解为形式类似的子问题(分治/减治)，核心则是在尚未得出结果时假装已经有了(“fake it 'til you make it”)。任何一个递归算法都有与之对应的循环算法，可能会相对更简单或者更复杂，反之亦然(通常递归写法更易于理解)。而纯粹的函数式编程语言中是没有循环的，只使用递归，且为应对递归深度问题会专门进行优化(尾调用优化)。Python未实现这类优化，默认限制递归深度为3000层(sys.getrecursionlimit())，超出会报错，必要时可调整该限制的具体取值。

分治与减治：两者名称相近，策略也类似，区别在于：减治是将问题依次转化为规模更小的问题，原问题的解可由新问题的解直接得到；分治法则是将问题依次分解为多个(规模更小的)子问题，原问题的解需要综合全部或部分子问题的解得出。换句话说，减治法每次递归都只有一个新问题，而分治法每次递归一般对应多个子问题。从这个角度看，减治法可理解为只有一个子问题的分治法ref。减治法中问题的规模可以依次减少一定量(可变)，或者缩小一固定因子；而分治法一般只考虑子问题规模缩小一定因子的情况。举例来说，插入排序和合并排序分别对应减治和分治，二分查找则可同时归于两者。分治策略的时间复杂度最好情况可达对数级，是很多高效算法的核心。

变治法：核心策略是将复杂的问题转化为相对简单的问题处理，听起来就是分治/减治法所做的，但分治法的重点是改变问题本身而不只是问题的规模：可以是直接转换问题，如借助堆处理排序问题；或是对数据进行预处理，如预先排序、取哈希值等。

动态规划：将复杂问题层层分解为子问题，综合子问题结果解决原问题，听起来还是与分治法很像🤣️。关键的区别在于动态规划的子问题间存在重叠，核心策略是缓存记忆重叠的子问题结果，避免重复计算，以空间换时间，只是这一简单的策略完全被动态规划这个华丽的名字给掩盖了。关于动态规划及贪心算法的更多介绍可查看这篇文章。

状态树搜索：可视为暴力穷举的改进，有策略的穷举搜索，常见算法有分支定界和回溯法，关于树搜索的更多算法可参考这篇文章。
分支定界(Branch and Bound)：“分支”即划分子问题，“定界”即通过分析子问题上(下)界判断是否剪枝，乍一听和分(减)治很像。根本的区别在于，无论分(减)治对问题的缩减还是变治对问题的变换都是基于问题空间的，而分支定界则是对状态空间/解空间(树)的划分与搜索，“分支”其实是划分解空间。从这个角度看，分支定界与回溯/试错更为接近，同为对解空间的搜索，同时相比暴力穷举又都采取一定策略进行优化。两者都将所有可能的解视为一颗树，树的根代表全集，每个分支为部分子集，层层细化直至一个具体的解，并在搜索时通过一些条件实现剪枝，实现对暴力穷举的优化。
分支定界法在探索任一分支前会首先估计该分支最优解的上(下)界，如果不能获得比之前更好的结果就直接舍弃，为此需始终记录当前已知的最优限制。具体实现上，基于队列和堆栈可分别实现广度优先(breadth-first)和深度优先(depth-first)的搜索，基于优先队列还可实现最佳优先(best-first)搜索。显然该算法依赖于对上(下)界的有效估算，否则算法将退化为暴力穷举。分支定界多用于组合优化，此时上(下)界一般可通过放宽变量的整数限制(使用连续变量)得到。
回溯法的基本做法是首先列举问题的一个部分解，并逐次扩展，最终给出所有可能的解。解空间树的树根为最小的部分解，所有可能的解都包含该部分解，因此代表解的全集；之后每层的分支都是对上一层节点部分解的扩展，对应对解空间的划分，层层扩展直至对应问题的一个具体解。搜索时，回溯法从根节点起按深度优先(depth-first)策略搜索解空间树，对每个节点首先判断其对应的部分解是否可扩展为问题的可行解：如果不能就直接舍弃；如果能先判断节点本身是否已是完整解，是就返回结果，否就对其继续扩展并重复前面的操作。显然该算法依赖于对任意部分解是否可扩展为可行解的快速判断，不能有效判断就将退化为暴力穷举。不同于分支界定只给出最优的一个解，回溯法可搜索出所有满足要求的解，因此除了用于组合优化，回溯法还是解决约束满足问题的重要工具，如数独、填字游戏、图着色、八皇后等。此外，回溯法还是逻辑编程语言的基础ref。

启发式算法：核心是由经验法则(rule of thumb)近似确定下一步优先探索(迭代)的方向，这些经验法通常是来自其他领域的“启发”，如遗传算法是受遗传基因的启发，进化算法是受物种演化的启发，其他还有模拟退火、粒子群、人工蜂群、蚁群、爬山等等。

Complexity

先借助例子对复杂度有一个直观的认识：对1百万条记录排序，假设计算机每秒可处理1百万记录，如果存在Θ(n)的算法，则1秒即可完成；如果采用Θ(nlogn)的快速排序，也只需20秒；而如果采用Θ(n2)的冒泡法则将需要接近12天时间！由此可见不同复杂度的巨大差别以及复杂度分析的意义。复杂度分析常见于算法分析和计算复杂度理论：前者指针对求解问题的特定算法的分析(涉及大O符号)，后者则要考虑解决问题的所有可能算法(涉及P, NP)。

Asymptotic Analysis

大O符号是复杂度分析中常用的标识，所代表的是，忽略不同计算机运算速度差异的常数因子，算法不依赖于具体硬件的渐近(n→∞)行为，也被称为渐进符号，算法分析中常见的有以下几种，具体的数学定义可参考维基百科。
符号 Θ O Ω o ω
意义 渐近紧确界/同阶(≈) 渐近上界(≤) 渐近下界(≥) 渐近非紧上界(<) 渐近非紧下界(>)
注：Θ表示同阶，例如复杂度Θ(n)意味渐进上下界均为线性阶，即同时满足O(n)及Ω(n)。

算法的实际表现依赖具体的问题情景(如数据的分布)，因此算法分析又分最好、最坏和平均情况，通常关注的是最差以及平均的复杂度。注意，这里的三种情况与上述渐近下界(Ω)、渐近上界(O)、渐近紧致确界(Θ)三个符号间不存在对应关系。大O符号作为表示函数渐进行为的数学概念，针对的是具体情况下的算法行为，任一符号都可用于最好、最坏和平均三种情况下的复杂度分析。

最后，虽然在构思程序时分析复杂度是有益的，但需要警惕过早优化代码，相比细小的速度提升，代码的可读性更重要，过早的优化是万恶之源(premature optimization is the root of all evil)。此外，在分析复杂度时通常会忽略常数，如O(10n)与O(n)没有区别，但程序需运行1天和10天的差别还是很大的。

以下展示了不同数据结构常见操作的复杂度，以及不同排序算法的复杂度。颜色由绿到红(　　　　　)依次对应复杂度由常数阶、对数阶、线性、线性对数到多项式/指数/阶乘。注意，对数阶复杂度log(n)可理解为log2(n)，通常涉及二分法，不过由于大O符号忽略常数倍差异，因此底数是无所谓的。

Binary Heap??

Data Structure Indexing Search Insert Delete
Array, List O(1) O(n) O(n) O(n)
Linked List,
Queue, Stack		 O(n) O(n) O(1) O(1)
Linked List O(n) O(n) O(1) O(1)
Queue, Stack – O(n) O(1) O(1)
Skip List Θ(logn) , O(n) Θ(logn) , O(n) Θ(logn) , O(n) Θ(logn) , O(n)
Hash Table – Θ(1) , O(n) Θ(1) , O(n) Θ(1) , O(n)
BST, KD Tree Θ(logn) , O(n) Θ(logn) , O(n) Θ(logn) , O(n) Θ(logn) , O(n)
B-Tree, AVL Tree,
Red-Black Tree		 O(logn) O(logn) O(logn) O(logn)
Cartesian Tree – Θ(logn) , O(n) Θ(logn) , O(n) Θ(logn) , O(n)
Splay Tree – O(logn) O(logn) O(logn)
Binary Heap – O(n) O(1), O(logn) O(logn)
Sort Algorithm Time(Best, Average, Worst) Space(Worst)
Quicksort Ω(nlogn) , Θ(nlogn) , O(n2) O(logn)
Mergesort Ω(nlogn) , Θ(nlogn) , O(nlogn) O(n)
Timsort Ω(n) , Θ(nlogn) , O(nlogn) O(n)
Heapsort Ω(nlogn) , Θ(nlogn) , O(nlogn) O(1)
Bubble Sort Ω(n) , Θ(n2) , O(n2) O(1)
Insertion Sort Ω(n) , Θ(n2) , O(n2) O(1)
Selection Sort Ω(n2) , Θ(n2) , O(n2) O(1)
Tree Sort Ω(nlogn) , Θ(nlogn) , O(n2) O(n)
Shell Sort Ω(nlogn) , Θ(nlog2n) , O(nlog2n) O(1)
Bucket Sort Ω(n+k) , Θ(n+k) , O(n2) O(n)
Radix Sort Ω(nk) , Θ(nk) , O(nk) O(n+k)
Counting Sort Ω(n+k) , Θ(n+k) , O(n+k) O(k)
Cubesort Ω(n) , Θ(nlogn) , O(nlogn) O(n)

Master Theorem

主定理(Master Theorem)：分治法时间复杂度
对于输入规模为nn的问题，假设使用分治法解决问题：每次递归，问题转化为aa个规模为n/bn/b的需进一步分解的子问题，直至子问题规模降至可直接解决。显然bb必须大于1，aa则可以等于1，aa取1时可视为减治。
以T(n)T(n)表示输入规模为nn的问题的运行时间(假设nn是bb的指数幂)，则有：

T(n)=aT(n/b)+f(n)T(n) = aT(n/b) + f(n)

其中f(n)f(n)代表分解子问题及合并子问题结果所需时间。
令α=log⁡baα = \log_b a，则主定理可表示为：

T(n)={Θ(f(n)),f(n)=Ω(nα+ε)Θ(nαlog⁡n),f(n)=Θ(nα)Θ(nα),f(n)=O(nα−ε)∗T(n) =\begin{cases} Θ(f(n)), & f(n)= Ω(n^{α+ε})\\ Θ(n^α \log n), & f(n)= Θ(n^α)\\ Θ(n^α), & f(n)= O(n^{α-ε})^* \end{cases}

*该条成立额外要求：∃c, s.t. af(n/b)≤cf(n)\text{\footnotesize *该条成立额外要求：} ∃c, ~ \text{s.t.} ~ af(n/b)≤cf(n)

三种情况分别对应于分解及合并子问题的计算量大于、等于、小于求解子问题本身的计算量，更多讨论可参考维基百科。以f(n)=Θ(nc),c≥0f(n)=Θ(n^c),c \ge 0为例：

T(n)={Θ(nc),c>αΘ(nclog⁡n),c=αΘ(nlog⁡ba),c<αT(n) =\begin{cases} Θ(n^c), & c > α\\ Θ(n^c \log n), & c = α\\ Θ(n^{\log_b a}), & c < α \end{cases}

二分查找，a=1,b=2,c=0a=1, b=2, c=0，T(n)=Θ(log⁡n)T(n)=Θ(\log n)
合并排序，a=2,b=2,c=1a=2, b=2, c=1，T(n)=Θ(nlog⁡n)T(n)=Θ(n\log n)
二叉树遍历，a=2,b=2,c=0a=2, b=2, c=0，T(n)=Θ(n)T(n)=Θ(n)
注：对数阶需c=α=0(a=1)c=α=0(a=1)，即分治只有一个子问题，且子问题分解合并计算量为常数阶；线性对数阶需c=α=1(a=b)c=\alpha=1(a=b)，即分治为aa个规模为n/an/a的问题，且子问题合并计算量为Θ(n)Θ(n)。

直观理解，最终计算包含求解最终子问题和逐级合并子问题两部分。最终需求子问题的总数量为alog⁡bn=nlog⁡ba=nαa^{\log_b n} = n^{\log_b a} = n^α，每个子问题求解为常数阶，求解子问题的总计算量为Θ(nα)Θ(n^α)。而对于分解及合并子问题，问题的数量会随递归而层层递增，输入规模则逐渐减少，假设n=bkn=b^k，当输入规模减至m=bjm=b^j时，对应问题数量为ak−ja^{k-j}，从而合并和分解子问题的总计算量为∑j=1j=kak−jf(bj)=ak∑j=1j=k(bc/a)j\sum_{j=1}^{j=k} a^{k-j} f(b^j) = a^k\sum_{j=1}^{j=k} (b^c/a)^j，求和部分为等比数列：

  • c>αc > α 则 bc/a>1b^c/a>1，结果为akΘ((bc/a)k)=Θ(bck)=Θ(nc)a^kΘ((b^c/a)^k) = Θ(b^{ck}) = Θ(n^c)
  • c=αc = α 则 bc/a=1b^c/a=1，结果为akΘ(k)=Θ(nαlog⁡n)a^kΘ(k) = Θ(n^α \log n)
  • c<αc < α 则 bc/a<1b^c/a<1，结果为akΘ(1)=Θ(nα)a^kΘ(1) = Θ(n^α)

与求解子问题的计算量合并，保留最高阶，忽略常数因子，即为前面的结果。
注：上述分析中，分解合并问题的计算量始终不低于求解子问题的计算量，前者是速度的关键。

对减治法可做类似分析：缩小固定因子对应于上述结果中a=1a=1的情况；减少固定量，aa同样为1，但没有了bb，时间复杂度可表示为T(n)=T(n−s)+f(n)T(n) = T(n-s) + f(n)。以插入排序为例，s=1,f(n)=Θ(n)s=1, f(n)=Θ(n)，而最终T(n)T(n)为Θ(n2)Θ(n^2)

最后，对常见分治问题复杂度做一个粗略总结：

  • 线性：只有一个子问题，问题每次减少常量，且子问题合并为常数阶，如数组遍历。若合并不是常数阶，以快速排序为例，合并复杂度O(n-s)，总体复杂度O(n2)。
  • 对数：只有一个子问题(最终子问题总数为1)，问题每次缩小常数倍，且子问题合并为常数阶，最常见的如二分查找。
  • 线性对数：每次分解为k个规模缩小k倍的子问题(最终子问题总数为n)，且子问题合并为O(n)，分解层数(递归深度)为O(logn)，最终总的复杂度为O(nlogn)，可以通过递归树很直观的理解，常见的有合并排序、快速排序等。
  • 指数：前面分析的分治算法中分解的各子问题是相同的，每次只需一个递归调用，而如果每次不止一个递归调用，如汉诺塔、幂集、斐波那契数列等，将需要指数级O(cn)操作。这其中一些问题本质上就是指数级的，另一些子问题间存在重复，可通过记忆化技术降低复杂度，如斐波那契数列。

扩展阅读：

Algorithms and Data Structures
The Most Important Algorithms - Christoph Koutschan
The 10 (classes of) Algorithms Every Programmer Must Know About
Computational complexity theory
Big O Cheat Sheet
Big O Poster