eecs 281 复习

Container and ADT

Stack

标准的 FIFO 结构
常用的 method 函数

push()
pop()
top()
size()
empty()

array 型 stack 的时间复杂度分析

push $O(1)$ $O (1)$ 对于一般情况; $O(n)$ $O (n)$
对于内存满了需要额外申请的情况
- 注意申请空间的时间复杂度是
  $O(1)$ ，而复制内容到新的数组的时间复杂度是 $O(n)$
pop, top, size, top 的时间复杂度都是 $O(1)$

摊还分析 amortized analysis

对于一个不一定要进行内存申请空间的vector，平均的push花费的时间复杂度是:

从 size = n 到 size = 2n 一共要 push n 次, 每次 O(1)
在 size = 2n 的时候要进行空间申请和复制，时间开销是 O(2n)
总花销 $O(1) \cdot n + O(2n)$ , 总步长 $n$ 那么平均复杂度是
$O(3) = O(1)$
也就是说 array 的 push 也是常数时间复杂度

link-list 型的时间复杂度

都是 $O(1)$ $O (1)$
- push 由于stack 的数据结构特点，一般只会在头上
  (head_pointer) 进行插入，因此时间复杂度为 $O(1)$
- size
  需要用一个额外的变量进行记录，如果没有这个变量，统计尺寸的时间复杂度是
  $O(n)$

array 和 link-list 的对比

虽然二者渐进分析 asymptotic
的表达式相似，但是从常数系数来说，array 的系数小，而且
link-list 需要的 overhead memory 更大

stl 实现 stack

std::stack
std::list 用链表实现
std::vector 用array 实现
std::deque

queue 队列

环形结构

队列为空: back_idx == front_idx
push: back_idx = (back_idx + 1) % capacity
pop: front_idx = (front_idx + 1) % capacity
空间申请: 也是满了之后进行 memory double
将原数组按照 front 到 end 的顺序排列到新的数组中

array 类时间复杂度分析

push: 申请空间的时间复杂度是 O(n), 一般 push 是 O(1)
pop, size, empty, front 都是 O(1) 复杂度

link-list 时间复杂度分析

需要一个指向链表末尾的 tail_ptr
因此每一步的时间复杂度是 O(1)

dequeue 和 vector 的区别

deque 有push_front 和pop_front 两种特殊的 method 但是
vector 没有
vector 有 [] operator, 时间复杂度是 O(1)

deque 的实现

deque 要求 link-list 是双向链表, 否则会过于低效
dequeue 在内存中的存储结构是 chunk
模式，也就是说是每一段作为一个
chunk，内部按照一般的array进行存储，deque 会用一个 map
结构存储每一个 chunk 开头的地址
- 地址解码方式: idx / chunksize 得到chunk id; idx %
  chunksize 得到 chunk 内相对行号
stl 支持通过 [] 访问指定位置的元素

priority queue

First In, High Priority Out

变量进入 adt
之后会被容器自带的比较函数分配到对应的优先级数字以及优先级坐标

不同实现方式的时间复杂度

implementation	insert	remove
unordered container	O(1) 直接插入	O(n) 线性查找之后remove
sorted container	O(n) 插入排序	O(1)
从对应位置(top) 删除
heap	log(n)	log(n)
array of link list	O(1)	O(1)

这里的 array of link list
指的是将优先级分为几个level，每个level 内遵循 fifo
规则，因此其复杂度是可以在常数内实现的

复杂度分析方法

影响因素

algorithm
implement details
cpu 和 memory 的硬件速度
compiler 及其编译标志
- -g3, -O3 会影响
input size 输入数据尺寸

哪些步骤算一步？

variable assignment
arithmetic operation
comparison
array indexing or pointer reference
function call
function return

`for-loop` 用时

初始化 O(1)
比较 $n+1$ 次
执行内部算法 n 次
因此一共 2n + 2 次

nested for loops

一般将 for 算作 2n + 2 次(可能 i 的增量不是1，要注意对应)
然后注意 for 内部的执行次数是一般方法得到的次数 * n^k, k
为嵌套的 for 层数

for(int i = 0; i < n; i++){
    for int (j = 0; j < n; j++){
        sum ++;
    }
}

第一层 for 有 2n+ 2 的步长
第二层 for 有 n(2n + 2) 的步长
最内层 sum++ 有 $n^2 \times 1$ 的步长

渐进符号 asymptotic notation

以下三个符号在无穷处都能收敛某一个值

f(n) = O(g(n)): $\frac{f(n)}{g(n)}< \infty$
f(n) = $\Theta$ (n): $\frac{f(n)} {g(n)}\in (0,\infty)$
f(n) = $\Omega$ (n): $\frac{f(n)}{g(n)} > 0$

摊还分析 amortized analysis

worst case 的一种分析方式
摊还分析的container push 操作的复杂度一定是 O(1) 吗?

如果容器的 size 设定是每常数 c 次 push
就申请一定的空间，那么其时间复杂度是 $\frac{(1 + \Theta(n)) + c\cdot \Theta(1)}{c} = \Theta(n)$
如果容器的 size 设定是每 n 次 push 2n 空间，那么复杂度是
$\frac{(1 + \Theta(n)) + n\cdot \Theta(1)}{n} = \Theta(1)$

算法速度的测量方法

分析的方式分类

analytically
- analyze the code itself
- recognize common algorithms/patterns
- base on recurrence relation
empirically
- measure runtime programmatically
- measure runtime using external tools
- test on inputs

时间测量函数

在 c++ 中提供了一个名叫 <chrono> 的库，一般使用
std::chrono::system_clock::now()
进行调用当前时间，但是这一步会消耗比较大的时间，因此多次调用这个函数，程序的速度就会变慢很多，这一点和 HAL_GetTick() 函数的原理类似
计时器清零: std::chrono::duration<double>::zero()

linux 时间测量脚本

/user/bin/time progName -options args (注意给 progName 加上
./ 前缀)
即在一般程序的前面加上一个 time 指令，会返回一个 runtime
report:
user time + system time + elapsed time + cpu occupied

user time: program 用时
system: os 使用程序的时间
elapsed: 从程序开始到结束的
计时器用时，可能包含了其他程序的时间
cpu: $\frac{\text{user + system}}{\text{elapsed}}$

内存测量工具 memory measurement

格式: valgrind ./prog -options
常用标志: --leak-check=full --show-leak-kinds=all
这个程序只能找到是否有泄漏，但是其memory地址对我们来说并没有什么用，我们只能知道main中存在new没有被delete

递归 recursion

尾递归 tail recursion

在每个函数的结尾调用下一层，本层之后没有其他任何操作
现代编译器会利用这个结构进行stack重复利用，因此其时间复杂度、空间复杂度和 iteration
的效果一致 (最后一步很多时候就是在 return 的里面)
因此尾递归适合用于一些stack size 很大的算法

主定理 master theorem

主要形式

T(n) = aO(\frac{n}{b}) + \Theta(n^c)

若 $a > b^c$ 则 $T(n) = \Theta(n^{\log_b a})$
若 $a = b^c$ 则 $T(n) = \Theta(n^c \log a)$
若 $a < b^c$ 则 $T(n) = \Theta(n^c)$
第四条件: 若余项为 $\Theta(n^{\log_b a}\log^k n)$ 那么 $T(n) \in \Theta(n^{\log_b a}\log^{k+1} n)$

c++ 的数组

固有缺点

array 的尺寸和数组本身分开存储
没有边界检查

1D 与 2D 数组

事实上都是按照 1d 的方式存储

`[]` operator 的解释

在 array 中, [] 操作符都会被解码为 a[i] = *(a + i),
因此，如果我们写为 i[a] 其解释结果会和 a[i]
一致而不会导致编译器报错

数组的定义

一般静态数组的定义并不能使用变量 n ，只能用 const
如果是动态数组，那么其尺寸的定义可以用变量

静态数组的好坏

优点

在命名域结束后会自动释放内存，不需要手动 delete
a[i][j] 可一步访问所求内存，不需要分两步走
缺点
对于较大的尺寸 n 不一定会有效，很有可能 crash
在 compile time 的尺寸一定
很难作为参数传入函数

动态数组的好处

优点

支持非矩形数组
支持 copying, swapping rows (就是用 swap 进行copy)
runtime 时候可以改变尺寸
缺点
需要对应 delete, 可能 crash 或者 memory leak
a[i][j] 的访问速度会比一般静态数组慢
解决方案是使用 stl 的 vector

Off-by-One 问题

如果声明一个数组为 array[sz], 那么其访问的范围为 [0,sz-1]

range-based-loop

1	for(auto& a : array){}

a 是数组 array 的每一个元素的 reference
也可以不用reference, 直接用值进行遍历

按值和 reference 遍历的区别:

按值遍历对于数组而言是只读操作，改变值并不会进入数组本身
性能开销：对于内存很大的数组，reference 遍历的性能会好很多

数组的复制

数组 container 的内部类型以及返回类型

container 的内部类型为 value (而不是ptr/ref)
返回元素是 reference (从而能更改原数组值)

数组复制的 ptr 所有权问题

对于拥有 ptr 的容器进行复制，我们会需要考虑指针的复制方法
1.如果每个容器的指针唯一，那么就不会出现多个指针指向同一个地址的问题
2. 要么就容器没有指针，不需要自己申请空间，有一个 bigbrother 或者垃圾收留中心进行内存垃圾检查

防御性编程 defensive programming

在 delete 的时候，我们需要额外执行一步将指针赋值为 nullptr, 因为如果要进行 double delete, 那么对于 nullptr 进行 delete 不会影响任何
在现代 C++ 编程中，经常建议使用智能指针（如 std::unique_ptr 或 std::shared_ptr）来管理资源

new constructor

如果一个动态数组的类型不是基本类型，那么使用 new type[4]
的时候会调用默认 constructor
同理，如果调用 delete[] 就会调用默认 destructor 函数

copy constructor

注意 type a = my_type_instance; 调用的是构造函数而不是
赋值函数

赋值函数的 copy-swap 方法

对于一个 assignment operator 而言，最好的实现流程是

使用 constructor 将传入对象复制为一个新的 instance temp
对 temp 的各个元素使用 std::swap
指令，这个指令可以快速交换两个元素，也可以快速交换两个指针(如果指针指向的是树结构也可以只交换两个树的跟节点指针，仍然能达到交换全部的效果)
return *this; 由于作为 operator 需要有返回类型,
我们还得这样写

优点

这样我们会将原来的对象的所有数据安全的转移到临时变量 temp
中, 再利用命名域的特性自动清除其中的内存(在结尾调用其析构函数), 这样内存会比较安全
且我们并不需要考虑自赋值的情况了(在原来的 assignment 里需要额外考虑自赋值的情况并且避开) 这里我们假设自我赋值然后会建立一个新的对象然后和自己进行交换

return value optimization (RVO)

在函数return的时候，传统的 c++ 编译器会将这一步处理为 copy
swap 即在返回值空间和返回对象之间进行 swap
并且让命名域结束的时候通过析构函数自动安全销毁来自原来在
对象中的元素

新概念 big 5

big 3:

distructor
copy constructor
overloaded operator=()
optimized 2:
copy constructor from r-val (这里主要指临时变量)
overloaded operator=() from r-val

STL 的使用

常用关键字

explicit

在构造函数前面加上 explicit 关键字，可以防止隐式类型转换
也就是在单个参数的类构造函数可能会被编译器隐式调用，即将一般参数等价为一个构造函数的输入，使用 explicit 会避免这个问题

mutable

在类中的成员变量前面加上 mutable 关键字，可以使得这个变量在 const 函数中也可以被修改

class A{
    mutable int a;
    const int b;
    void change() const{
        a = 1;
        b = 1; // error
    }
}

stl 的指针问题

stl 会尽量少的使用指针和动态内存分配问题
调试时间能够极大程度的减小
可对多个数据类型使用同一个算法

stl 的速度

撰写stl的核心目标是 time performance

list 容器

list<>: 双向链表, .size() 时间复杂度是 O(1)
slist<>: 单向链表, .size() 时间复杂度是 O(n)
- 内部存在 smart pointer
forward_list<>: 单向链表, .size() 并不存在

迭代器 iterator

迭代器是 generalized pointer，我们可以简单的将迭代器理解为一个指针
对于 *it++ 会被分解为两步：*it 和 it++ 即访问当前指针的元素然后进行位移

迭代器的分类

io类：

input_iterator: 只读，只能一次遍历
- 对应常数迭代器: vec.cbegin() 即迭代器只能访问读元素但是不能更改元素
output_iterator`: 只写，只能一次遍历
可多次访问类：(可多次遍历，可以读写数组内容)
forward_iterator: 读写，可以多次遍历
bidirectional_iterator: 双向，可以前后遍历
reverse_iterator: 反向，可以反向遍历
- rev_it++ 表示向前遍历
- 边界条件是 rev_it == vec.rend(), 以及 rev_it = vec.rbegin()
random_iterator: 随机，可以随机访问，支持索引访问
- 索引: auto it = vec.begin(); cout << it[2]; 表示访问第三个元素
- 随机访问: 支持 it += 2 或者 it -= 3 之类的操作
- 支持访问两个随机迭代器之间的距离: it1 - it2

container 的使用

STL 中的许多算法，例如 std::sort、std::copy 等，都是以迭代器的方式来接受参数可以对一个容器的一部分（而不是整个容器）进行操作，而不是直接对整个容器进行操作
迭代器范围 是通过两个迭代器来定义的，第一个迭代器是起始点，第二个迭代器是结束点（不包含该结束点）
迭代器范围不要求容器支持随机访问。在一些非随机访问容器（例如 std::list 这样的双向链表）中，我们仍然可以使用迭代器范围来表示某个区间的元素并进行操作。与使用索引不同，迭代器不要求容器的内存是连续的。因此，迭代器可以在链表等数据结构上有效工作（索引通常只适用于支持随机访问的容器）
使用迭代器进行遍历通常比使用索引更快, 例如对于一个链表, 迭代器则可以直接通过顺序遍历来获取下一个元素，避免了重复从头遍历的开销

例：反序数组的构造

我们使用反向迭代器来实现数组的构造:

1 2	vector<int> vec = {1, 2, 3, 4, 5}; vector<int> vec_rev(vec.rbegin(), vec.rend());

v.begin() 与 begin(v) 的区别

前者适用于所有 stl 容器，而后者还额外适用于原生 array
注意 begin(v) 对于 v 为 stl 的时候返回的是 iterator, 而对于原生 array 返回的是指针 (当然一般数组的指针也可以支持很多stl函数的迭代器操作)
因此后者是更好的选择

for-range 对比 iterator 的优势

对于遍历一个线性容器，我们使用 for-range 会比 iterator 更加简洁

1
2
3

for (auto &x : vec){
    cout << x << " ";
}

这一步实际上会被解释为 for(auto it = vec.begin(); it != vec.end(); it++)
但是这样写不会有 ambiguity 问题

vector 的额外空间占用

在 stl 中我们存储一个 vector 会用到 3 个额外指针:

begin allocated memory
end allocated memory
end used memory
那么对于一个 3 维向量 vector<vector<vector<int>>> vec(a,b,c) 那么我们一共需要有 $3 + 3a + 3ab$ (即 3 * (1 + 层数 + 层数 * 行数))
因此我们可以考虑改变行列顺序来减少 overhead 的内存占用

Functor 仿函数

定义一个类或者一个 struct 并且内部只定义一个函数 operator()
且一般返回一个 bool 进行比较
常用于一些比较方法的输入

递增串的构造

在 std 中存在函数 std::iota() 用于构造一个递增的数组
输入参数为 forward_iterator begin, forward_iterator end, T val 即将 [begin, end) 范围内的值从 val 开始递增 1 的数组

lambda 表达式

lambda 表达式是一个匿名函数，可以在函数内部定义，用于简化代码，也能提高代码的可读性
可以被作为参数传入函数中

随机数 randomization

堆和堆排序 heap

树结构 tree

树是一种连接的 graph 且没有 cycle
任意两个 node 之间存在唯一一个最短的路径

terminology

root: top most node in the tree
parent: immediate predecessor
child: node where current node is parent
ancestor: parent of a parent
descendent: child of a child
internal node: a node with children
leaf node: node without children
height: 表示节点到叶子的距离 (最大值)
- 可以用递归的方法
- height(node) = max(height(left_son) , height(right_son)) + 1
size: 节点的数量（包含根、叶子）
- size(node) = size(left) + size(right) + 1
depth: 到根节点的距离
- 用递归的方法计算
- depth(node) = depth(parent) + 1
complete binary tree:
每一层要么填满要么就是从左到右填而不存在空位

完成树 (堆) 的节点访问方式

parent: $i/2$
left son: $2i$
right son: $2i + 1$
if leaf: $2 * i > size$

最大堆 max heap

满足完成树的结构
每个节点大于左右子
这种结构能够轻松访问最极端的元素

bottom-up fixing (以大顶堆为例)

将某一个元素向其 parent node
进行比较如果大于那么交换并且对 parent 执行递归操作直到 root
如果在其中一步发现已经不需要进行交换，那么可以及时退出从而降低时间复杂度
从最差情况下进行考虑，这里的时间复杂度是 $O(\log n)$
常用于插入算法

插入操作

将某一个元素进行插入，即将变量放入最后，再执行 fixUp 指令

top-down fixing

从根节点开始，向左右节点进行比较，如果根节点小就进行交换

如果左<右那么就和右进行交换; 如果左 > 右
那么就和左进行交换; 如果左 = 右就默认和左进行交换

如果到达根节点或者在某一个节点的左右子节点都不大于本节点那么我们就可以跳出这个函数了

时间复杂度是 $O(\log n)$

常用于删除算法

PQ 的删除

将top元素pop之后将最后一个元素放到堆顶并且执行 fixdown 操作

堆排序

建堆 heapify

我们使用 bottom-up fix-down 的操作，从最后一个interal node 开始
(即 size / 2) 不断对每个node进行从 node 到 last 的 fixdown
操作

时间复杂度 $O(n)$

堆排序内部实现

根据堆的特性，我们一般将最大堆排序成为递增数组
我们每一次将堆排序获得的 top 值 (最极端值) 放到整个数组的最后
(也就是利用堆的特性将每次选出来的极端值放到最后从而实现有序)
当然我们也可以放到最前面实现递减效果，但是这会导致我们的堆root会移动会异常复杂
时间复杂度 $O(n\log n)$ 每一步的时间复杂度是 $O(\log n)$

查找算法 Searching Algorithm

对分查找 binary search

在一个一维有序数组中，我们可以通过对分坐标的方法查找对应元素的位置，时间复杂度 $O(\log n)$
但是使用 stl 的故有算法 bsearch() 的效果只能返回已有数组中是否存在

优化策略 optimization

由于 == 的可能性数非常小，因此要少考虑这种情况，而应该多考虑 > <

这个做法能将时间复杂度减小一半

将 == 放入不等号形成 >= 或者 <=
从而一直使用二分数组

`lower_bound()` 下界查找

将输入元素作为 lower_bound 并且返回第一个不小于此
lower_bound 的元素

输入参数是 vec.begin(), vec.end(), val

`upper_bound()` 上界查找

返回第一个不大于此 upper_bound 的元素

`equal_range()`

并查集 union-find search

union 并集操作

一般的并集操作要将两个集合合并且保留二者的故有顺序
集合各个操作的时间复杂度

method	asymptotic
initialize	$O(1)$ 或者 $O(n\log n)$
clear	$O(1)$ 表示 array 下直接删除; $O(n)$ 表示 linked-list 类型的删除
isMember	$O(\log n)$ 就是一步查找算法
copy	$O(n)$
set_union	$O(n)$ 需要线性遍历两个数组
set_intersection	$O(n)$

并查集数据结构

对于每一个数据都有其自身数值以及其represent数值

那么判断两个数据是否在一个集合中就是看二者的represent
值是否相同

对两个集合进行 union 的时候默认对 cardinality 较小的集合更改 representative

也就是将较小的集合的 root 元素的 represent 指向较大集合

`find` 方法

从某个元素 j 开始不断沿着 represent 进行跳转直到 root

并且沿路不断更改 represent 的值

时间复杂度

排序算法 Sorting Algorithm

基本排序算法 elementary sort

排序算法的容器分类

array
linked list

排序算法的复制分类

internal sort: 元素可见，可以接受 O(1) 复杂度访问元素
indirect sort: 序号可见，常用于元素复制比较困难的情况
external sort: 元素在一个disk里面不可轻易变换，且每一部分内存常常按照 block 的形式存储；当数据量非常大，大到无法一次性装入内存时，就需要使用外部排序

评价排序算法的三个角度

时间复杂度
空间复杂度
稳定性
- elementary sort 的稳定性往往很好
- 对于多个关键因素排序十分重要
- 一种判定方式：对于排序相同的元素之间相对位置不发生变换

排序算法的分类

non-adaptive
adaptive: 对不同输入的表现效果不同

冒泡排序 bubble sort

std::sort(begin(a), end(a))
每一轮将最大/最小值放到一边，比较的元素是相邻元素
adaptive 策略: 如果某一次 pass 并没有发生任何交换，说明 array 已经有序，直接退出
时间复杂度: $\frac{n^2}{2}$

好坏情况分析

最差情况: 比较 $\frac{n^2}{2}$ 次，并且交换这些次数(完全反顺序)
最好情况：比较 $\frac{n^2}{2}$ 次但不发生交换

adaptive

最坏情况: 不变
最好情况: 0 次交换， n 次比较

优点

simple implement and understand
在前几步pass的时候也完成了部分排序内容
稳定
adaptive 的方法简单

缺点

$O(n^2)$ 的时间复杂度
比高级排序算法慢

选择排序 selection sort

每次找到 array
中的极值并且和边界进行交换，每次都至多会发生一个元素的交换
adaptive 策略: 如果极值等于自己，则不发生交换
(这个优化的非常有限)

优点

最小化复制量，很适合复制成本极高的数组
对于较小的 n 的效率很高

时间复杂度分析

$\Theta(n^2)$ 的时间复杂度
时间基本和 preorder 无关
- 对于基本有序 array, 有相等优先级 array, 以及
  随机分布的 array 的排序效果一致
sort 不 stable
- 由于相同元素的排布顺序并不知道，有可能发生相对位移

插入排序

将数据分成两队:
有序和未排序，有序部分不断增大，未排序部分逐步减小
每次将一个选中的数据插入到有序数组中
non-adaptive 模式的时间复杂度
- 最差 $\frac{n^2}{2}$ 比较次数, 交换次数
- 平均 $\frac{n^2}{4}$ 交换次数
时间复杂度对于输入数据顺序不敏感

优化策略

采用 move 而不是 swap 即 a[j] = a[j - 1]; 这一步
采用 while 而不是 for + break 模式
sentinel 哨兵法: 将不常用的边界判定 j > left
改成先找到最小值，将其放到最左边作为哨兵
(冒泡排序的一次pass) 然后将剩下的元素逐步插入到最前面
(第二次排序从第三个元素开始)

优化策略的优点分析

更高效的数据处理，copy 需要的时间是 swap 的 1/3
更少的比较和复制只在小于的时候进行插入

adaptive 结果分析

比较次数

最差情况下 $\frac{n^2}{2}$ 次比较
平均 $\frac{n^2}{4}$ 次比较
最好情况下 $n$ 次比较
复制次数
最差情况下 $\frac{n^2}{2}$ 次比较次数
平均情况下 $\frac{n^2}{4}$ 次比较次数
最好情况下 $n$ 次比较次数

运行时间对输入十分敏感

算法优点

运行时间依赖于初始顺序
稳定
算法可以微调
是在尺寸较小的时候的最优算法

缺点

时间复杂度用渐进表示仍然是 $\Theta(n^2)$

基本排序算法的总结

时间复杂度正比于
- 比较次数
- 交换次数
基本排序算法都是二次时间复杂度 (worst / average case)
- 在较有序数组的排序平均效果更好

3.插入排序、冒泡排序使用的是线性比较次数和交换次数，拥有常数的比较次数上界
(和原数组中 inversion 逆序对的数量相关)
- 因此我们称插入排序和冒泡排序对于一个几乎有序数组的排序效果是非常好的

4.插入排序的时间复杂度对于较大的输入且较无序数组的时候会有一个常上界
- 插入排序的效果取决时间复杂度
- 对于一个已经有序的数组进行新元素插入，效果最好的就是插入排序

桶排序 counting sort

分三次进行

第一次记录每个元素的数量
第二次计算每个元素开始的位置 (用第一次的尺寸进行累加得到)
第三次将结果返回到原数组中进行赋值

使用限制

当且仅当 key 的数量有限且较少
最大的 key 受到架构的位数限制

复杂度分析

时间复杂度是 $O(n+k)$ 其中 $n$ 表示数组长度， $k$
表示桶的数量
空间复杂度也是 $O(n+k)$
稳定
常用于索引排序 radix sort

`std::sort()` 函数的使用

参数 parameters

两个 iterator，一个记录开头一个记录结尾
一个自然排序的数组 (要支持有限度比较 $<$ )

Functor 作为比较依据

ascending: 递增
descending: 递减

快速排序

一般排序算法的不足之处:

对每一对元素都进行大小比较
- 这会导致比较获取的信息量很小
- 我们从对分查找进行分析: 如果从 $n/2$
  个点进行信息收集，那么其信息量会很大(这样数据可以成
  $\log n$ 复杂度)
基本算法往往只会将元素移动一个位置
- 对于相距很远的数组，其效果就有点慢
- 选择排序直接将元素移动到其最终的位置一步到位花费的时间精力都太多了

分治算法解决快速排序

base case: 如果数组长度是 0 或者 1 那么直接返回
递归步骤:
1. 猜测一个 elt 元素用来给 array 进行 partition 要满足每一次排序逆序对的数量都会减少
2. 我们这里假设选中elt并且将其放入对应的位置之后，其左边的数据都小于 elt, 右边的数据都大于 elt
3. 接下来接着递归左右两个部分
  从上述的要求来看，我们最主要的是拿到数据的 median 作为 elt
  但是选中中位数的步骤会占用时间复杂度，事实上简单使用某个元素即可

并不能保证这里选中的是最合适的数

partition 执行方式

从左到右找到低一个大于等于 pivot 的元素
从右到左找到第一个小于 pivot 的元素
如果 left < right 说明二者并没有相遇，那么交换二者的位置
如果 left >= right 说明遍历完了，那么将 pivot 和 left 交换

优化方式 better partition

为了防止出现最初有序的数组经过我们的排序重复工作导致效率低下，我们可以避开这种初次有序的情况: 将 pivot 选择为中间的数，开始的时候将选中的数据和最后的元素进行交换，从而再从前面开始快速排序
但是问题是这样的渐进分析表达式并不会发生变化，只能避免已经有序的数组重复劳作的问题

时间复杂度 time complexity

worst: $O(n^2)$ $O (n^{2})$
- 每次选中最大或者最小的数
- 对于一个长 n 的数组其最差的可能性数为 $2^n$
best: $O(n\log n)$ $O (n lo g n)$
- 每次都能选中位数
average: 一般在 $2n\log n - 1.39n \log n$ 即 $O (n\log n)$

空间复杂度 space complexity

由于我们会用到两个数组的递归（左右数组）因此上面那个递归并不是尾递归，因此我们需要花费比较大的stack 空间进行选取

优点 pros

平均时间复杂度是 $O(n\log n)$
较短的内部循环 $O(n)$
内存利用效率高 (只需要内部内存占用)
被学界完全认知和分析过

缺点 disadvantage

最差情况下 $O(n^2)$ 复杂度
不稳定
partition 很 fragile (如果写代码的时候出现边界问题很容易出现 segment fault)

更好的优化方式

将尺寸较小范围内的数组排序改用 insertion sort
三数中值法: 选取三个数中的中值作为 pivot
1. 定量分析最差情况: 这里我们定义最差情况是每次选中最边界的情况，那么标准情况选中边界元素的概率是 $\frac{2}{n}$ ;
2. 如果3数中值法, 我们选中最不好的情况 (第二大或者第二小) 的概率是 $\frac{1}{n \cdot (n-1)}$ 小了很多

内省排序 introsort

一般情况下使用 quick sort
在一定深度处改用堆排序，这样稳定性能上来

归并排序 merge sort

分而治之思想

合并两个数组

将两个数组合并起来，就是线性将两个数组遍历，对比大小然后将较小的值填入
时间复杂度 $\Theta(n)$
这个合并的步骤我们称为 stable sort, 也就是 std::stable_sort<>()
可以利用 linked-list 实现、外部内存以及 parellel sorting

主定理解决

时间复杂度的递归表达式为:

T(n) = 2T(\frac{n}{2}) + \Theta(n)

由于关系 $\log_2 2 = 1$ , 因此总时间复杂度是 $\Theta(n\log n)$

优点

稳定
能够连片获取数据
1. 不需要随机获取数据
2. 对于linked list, external memory 与 parallel sorting 非常友好

缺点

最好情况下的时间复杂度是 $\Omega(n\log n)$ $Ω (n lo g n)$
1. 即对于输入不敏感
需要额外的内存 $\Theta(n)$
在一些特定的输入情况下比 quick sort 慢

bottom-up 归并排序

其实我们可以利用 size 和 2 的指数进行快速分类排序，也就是每个左节点的开始位置是 left + 2^k 那么每次就是对内部进行排序 (即将2数组合并)

void merge_sortBU(Item a[], size_t left, size_t right){
	for(size_t size = 1; size <= right - left; size *= 2){
		for (size_t i = left; i <= right - size; i += 2*size){
	      merge(a, i, i + size, min(i + 2*size, right));
	    }
	}
}

eecs 281 复习

Container and ADT

Stack

array 型 stack 的时间复杂度分析

摊还分析 amortized analysis

link-list 型的时间复杂度

array 和 link-list 的对比

stl 实现 stack

queue 队列

环形结构

array 类时间复杂度分析

link-list 时间复杂度分析

dequeue 和 vector 的区别

deque 的实现

priority queue

不同实现方式的时间复杂度

复杂度分析方法

影响因素

哪些步骤算一步？

for-loop 用时

nested for loops

渐进符号 asymptotic notation

摊还分析 amortized analysis

算法速度的测量方法

分析的方式分类

时间测量函数

linux 时间测量脚本

内存测量工具 memory measurement

递归 recursion

尾递归 tail recursion

主定理 master theorem

c++ 的数组

固有缺点

1D 与 2D 数组

[] operator 的解释

数组的定义

静态数组的好坏

动态数组的好处

Off-by-One 问题

range-based-loop

按值和 reference 遍历的区别:

数组的复制

数组 container 的内部类型以及返回类型

数组复制的 ptr 所有权问题

防御性编程 defensive programming

new constructor

copy constructor

赋值函数的 copy-swap 方法

优点

return value optimization (RVO)

新概念 big 5

STL 的使用

常用关键字

explicit

mutable

stl 的指针问题

stl 的速度

list 容器

迭代器 iterator

迭代器的分类

container 的使用

例：反序数组的构造

v.begin() 与 begin(v) 的区别

for-range 对比 iterator 的优势

vector 的额外空间占用

Functor 仿函数

递增串的构造

lambda 表达式

随机数 randomization

堆和堆排序 heap

树结构 tree

terminology

完成树 (堆) 的节点访问方式

最大堆 max heap

bottom-up fixing (以大顶堆为例)

插入操作

top-down fixing

PQ 的删除

堆排序

建堆 heapify

`for-loop` 用时

`[]` operator 的解释

`lower_bound()` 下界查找

`upper_bound()` 上界查找

`equal_range()`

`find` 方法

排序算法的容器分类

排序算法的复制分类

`std::sort()` 函数的使用