大师定理

分治策略对应的递推式，通常（尽管不总是）形如：T（n）= a * T(n/b) + O(f(n))

(原问题被分为a个规模均为n/b的子任务；任务的划分、解的合并耗时f(n))

对于第一三区块，T（n）中 f（n） 与 n ^ ( log(b) a ) 哪一个大就取哪一个

若 f(n) = O(n^(log(b)a-ε)) , 则 T(n) = Θ(n^(log(b)a))

• Kd-search : T(n) = 2 * T(n/4) + O(1) = O(n^(1/2))

若 f(n) = Θ(n^(log(b)a) * log^(k)n) , 则 T(n) = Θ(n^(log(b)a) * log^(k+1)n)

• Binary search: T(n) = 1 * T(n/2) + O(1) = O(logn)
• Merge sort : T(n) = 2 * T(n/2) + O(n) = O(n * logn)
• STL Merge sort : T(n) = 2 * T(n/2) + O(n * logn) = O(n(logn)^2*）

若 f(n) = Ω(n^(log(b) a+ε) , 则 T(n) = Θ(f(n))

• Quick select (average case) : T(n) = 1 * T(n/2) + O(n)

抽象数据类型(ADT) VS 数据结构(DS)

抽象数据类型 = 数据模型 + 定义在该模型上的一组操作

​ 抽象定义 外部逻辑特性 操作&语义

数据结构 = 某种特定语言，实现ADT的一整套算法

​ 具体实现 内部的表示与实现 完整的算法

​ 多种实现 与复杂度密切相关 要考虑数据的具体存储机制

c/c++中，数组（array）A[ ]中的元素与 [0,n) 内的编号一一对应

反之，每个元素均由非负编号唯一指代，并可直接访问

A[i] 的物理地址 = A + i * s 故称线性数组

向量（vector）是数组的抽象与泛化，由一组元素按线性次序封装而成

各元素与 [0,n) 内的秩 (rank) 一一对应 //寻秩访问(call-by-rank)

元素的类型不限于基本类型

操作，管理维护更加简化，统一和安全

可更便捷地参与复杂数据结构的定制和实现

操作	功能	适用对象
size()	报告向量当前规模(元素总数)	向量
get(r)	获取秩为r的元素	向量
put(r,e)	用e替换秩为r元素的数值	向量
insert(r,e)	e作为秩为r元素插入，原后继元素依次后移	向量
remove(r)	删除秩为r的元素，返回该元素中原存放的对象	向量
disordered()	判断所有元素是否已按非降序排列（统计逆序对）	向量
sort()	调整各元素位置，使之按非降序排列	向量
find(e)	查找目标元素e	向量
search(e)	查找目标元素e，返回不大于e且秩最大的元素	有序向量
deduplicate()	剔除重复元素	向量
uniquify()	剔除重复元素	有序向量
traverse()	遍历向量并统一处理所有元素，处理方法由函数对象指定	向量