open-courses
  • 公开课笔记
  • CMU 15-445/645 Database Systems
    • Relational Data Model
    • Advanced SQL
    • Database Storage
    • Buffer Pools
    • Hash Tables
    • Tree Indexes
    • Index Concurrency Control
    • Query Processing
    • Sorting&Aggregations
    • Join Algorithms
    • Query Optimization
    • Parallel Execution
    • Embedded Database Logic
    • Concurrency Control Theory
    • Two Phase Locking
    • Timestamp Ordering Concurrency Control
    • Multi-Version Concurrency Control
    • Logging Schemes
    • Database Recovery
    • Introduction to Distributed Databases
    • Distributed OLTP Databases
    • Distributed OLAP Databases
  • UCB - CS162
    • OS intro
    • Introduction to the Process
    • Processes, Fork, I/O, Files
    • I/O Continued, Sockets, Networking
    • Concurrency: Processes & Threads
    • Cooperating Threads, Synchronization
    • Semaphores, Condition Variables, Readers/Writers
    • Scheduling
    • Resource Contention & Deadlock
    • Address Translation, Caching
    • File System (18,19,20)
    • Distributed Systems, Networking, TCP/IP, RPC (21,22)
    • Distributed Storage, Key-Value Stores, Security (23)
    • Security & Cloud Computing (24)
    • Topic: Ensuring Data Reaches Disk
  • MIT - 6.006
    • Sequence and Set Interface
    • Data Structure for Dynamic Sequence Interface
    • Computation Complexity
    • Algorithms and Computation
    • Structure Of Computation
    • Graph & Search
    • Tree & Search
    • Weighted Shortest Paths
    • String Matching, Karp-Rabin
    • Priority Queue Interface & Implementation
    • Dictionary Problem & Implementation
    • Sorting
    • Dynamic Programming
    • Backtracking
    • Self-Balancing Tree
  • MIT - 6.824
    • 2PC & 3PC
    • Introduction and MapReduce
    • RPC and Threads
    • Primary/Backup Replication
    • Lab: Primary/Backup Key/Value Service
    • Google File System (GFS)
    • Raft
    • Lab: Raft - Leader Election
    • Lab: Raft - Log Replication
  • Stanford-CS107
    • 原始数据类型及相互转化
    • 指鹿为马
    • 泛型函数
    • 泛型栈
    • 运行时内存结构
    • 从 C 到汇编
    • 函数的活动记录
    • C 与 C++ 代码生成
    • 编译的预处理过程
    • 编译的链接过程
    • 函数的活动记录续、并发
    • 从顺序到并发和并行
    • 信号量与多线程 1
    • 信号量与多线程 2
    • 复杂多线程问题
    • 函数式编程 - Scheme 1
    • 函数式编程 - Scheme 2
    • 函数式编程 - Scheme 3
    • 函数式编程 - Scheme 4
    • 函数式编程 - Scheme 5
    • Python 基础
  • MIT - 6.001 - SICP
    • 什么是程序
    • 程序抽象
    • 替代模型
    • 时间/空间复杂度
    • 数据抽象
    • 高阶函数
    • Symbol
    • 数据驱动编程与防御式编程
    • 数据抽象中的效率与可读性
    • 数据修改
    • 环境模型
    • 面向对象-消息传递
    • 面向对象 - Scheme 实现
    • 构建 Scheme 解释器
    • Eval-Apply Loop
    • Normal Order (Lazy) Evaluation
    • 通用机
    • 寄存器机器
    • 子程序、栈与递归
    • 在寄存器机器中执行
    • 内存管理
  • MIT - 6.046
    • Randomized Algorithms
    • Skip Lists
  • System Design
    • Twitter
    • Cache Consistency & Coherence
  • DDIA 笔记
    • Replication
    • Transactions
    • The Trouble with Distributed Systems
    • Consistency & Consensus
  • Papers We Love
    • Consistent Hashing and Random Trees (1997)
    • Dynamic Hash Tables (1988)
    • LFU Implementation With O(1) Complexity (2010)
    • Time, Clocks, and the Ordering of Events in a Distributed System (1978)
    • Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
    • Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
  • Release It 笔记
    • Anti-patterns & Patterns in Microservice Architecture
  • Database Design
    • Log Structured Merge (LSM) Tree & Usages in KV Stores
    • Prometheus
Powered by GitBook
On this page
  • 什么是 Randomized Algorithms
  • 特征:
  • 分类:
  • 举例:
  • Matrix Product Checker
  • Quicksort
  • 参考
  1. MIT - 6.046

Randomized Algorithms

什么是 Randomized Algorithms

特征:

  • 通过生成随机数来决定算法的走向

  • 同样的输入在不同的执行中可能

    • 运行不同的步骤 (步骤的数量、具体执行内容都可能不同)

    • 产生不同的结果

分类:

  • Monte Carlo: 时间复杂度为 polynomial 以内,结果在大概率(with high probability)情况下正确

  • Las Vegas: 时间复杂度的期望为 polynomial 以内,结果总是正确的。

举例:

Matrix Product Checker

问题描述:

给定 n × n 矩阵 A、B、C,验证 A × B = C 是否成立

普通解法:直接计算 A × B = C

  • Simple Algorithm: O(n^3) multiplications

  • Strassen: multiply two 2 × 2 matrices in 7 multiplications: O(n^2.81)

  • Coppersmith-Winograd: O(n^2.376)

可以做到 O(n^2) 吗?

Frievald's Algorithm (Monte Carlo)

本算法能够做到:

  • 如果 A × B = C,那么 Pr[output=YES] = 1

  • 如果 A × B ≠ C,那么 Pr[output=YES] ≤ 1/2,即 False Positive Rate

这样,若 k 次运行结果都是 YES,那么 False Positive 的概率将达到 (1/2)^k,因此这是一个 Monte Carlo 算法。

过程:

任意选择一个二值向量 r,向量中的每个元素都以 1/2 的概率取值为 1,1/2 的概率取值为 0 。如果 A(Br) = Cr,输出 YES,否则输出 NO

分析:

Quicksort

Basic Quicksort

算法

始终选择 A[1] 或 A[n] 作为 pivot

def quicksort(A, start=1, end=n):
    m = partition(A)          # O(n)
    quicksort(A, start, m-1)
    quicksort(A, m+1, end)

def partition(A):
    pivot = A[1]
    # ...

分析

如果输入是已经顺序或逆序,partition 会将所有元素放在 pivot 的同一边,此时:

空间复杂度在 in-place 情况下可做到 O(1)

Pivot Selection Using Median Finding

使用 Median Finding 算法可以保证在 θ(n) 时间复杂度下,获得数组的中位数,这样每次 partition 都能完美地将数组分成两部分,此时:

然而由于 Median Finding 较为复杂,虽然时间复杂度在 θ(n),但常数项较大,在实际运用中并不适用,通常要逊色于 mergesort。

Randomized Quicksort (Las Vegas)

使用随机选取任意元素作为 pivot 的策略,时间复杂度的期望为 O(nlgn),分析见 CLRS p.181-184。本课尝试分析该算法的一个变种:Paranoid Quicksort

"Paranoid" Quicksort (Las Vegas)

Good/Bad Pivots

可以看出选中 good pivot 的概率≥ 1/2,而 good pivot 中最差的两个分别在交界处,若选中它,问题将被分成大小分别为 (1/4)n 及 (3/4)n 的子问题。使用问题树分析:

本图有一定的误导性,实际上这是一个不平衡的树,树的深度从左往右逐渐递增。

由于选中 good pivot 的概率≥ 1/2,因此每次 pivot selection 执行的次数的期望:

E(#iterations) ≤ 2

所以推导公式为:

从图中可以看出,树的高度最高位 log(4/3)(2cn),因此最终时间复杂度的期望 T(n) = θ(nlgn)。

参考

Previous内存管理NextSkip Lists

Last updated 6 years ago

只要证明所有的二值向量中,至多有一半能在 A × B ≠ C 的情况下,使得 output=YES,证明过程具体见。

、

这里
video
lecture note
图 1 - Basic Quicksort 的时间复杂度分析
图 2 - Median Finding + Basic Quicksort 的时间复杂度分析
图 3 - Good/Bad Pivots
图 4 - SubProblem Tree
图 5 - Paranoid Quicksort Formula