algorithm-analysis-and-design
-
Hashing I 哈希 ChatGPT-summarized
下面是完全兼容 Obsidian 的 Markdown + LaTeX 版本（已清理所有非标准标记，可直接粘贴）： 2. (T[k]) 存的是 record，不是 key 定义： $$ T[k] = \begin{cases} x & \text{if } key[x] = k \ \text{NIL} & \t...
-
Hashing I 哈希
Direct-Access Table 直接寻址表 算法实现 存在问题 Direct-access table = 用空间换时间的极限方案： 用一个巨大数组，实现真正的 Θ(1) 查找，但通常空间不可接受。 为了解决空间的不可接受性, 推出Hashing Table Hashing Table 哈希表 哈希表由两...
-
Trick for Analyzing Recursive Time Complexity
$T(n)=T(an)+T(bn)+O(n)$ if $a+b=1$: $T(n)=O(nlogn)$ else if $a+b<1$: $T(n)=O(n)$
-
Order Statistic 顺序统计量
核心任务: Top-K问题: 在一个数组中找第k小/大的元素 实现方法: 1. Quick Select 快速选择 2. BFPRT - Median of Medians BFPRT选择算法 总结 Quick Select 其实就是只走一边的Quick Sort. Quick Select 虽然worst ca...
-
BFPRT - Median of Medians BFPRT选择算法
核心任务: Top-K问题: 在一个数组中找第k小/大的元素 隶属于任务: Order Statistic 顺序统计量 参考方法: Quick Select 快速选择 算法实现: step1: 分组, 5个元素一组 step2: 找每组的中位数(给每组的5个数排序) step3: 找中位数中的中位数pivot s...
-
Quick Select 快速选择
核心任务: Top-K问题: 在一个数组中找第k小/大的元素 隶属于任务: Order Statistic 顺序统计量 参考方法: Divide & Conquer 分治 Quick Sort 快速排序 算法实现: step1: 随机选择一个pivot step2: 将数组分为3部分 $O(n)$ step3: ...