A Survey of Common Running Times慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

下面讨论一些常用的运行时间

线性时间 O(n)

即运行时间至多是输入规模的常数倍

我们看下面的例子

计算a_1…a_n 这n个数的最大值

第一步 a_1 赋值给 max

第二步从 i = 2 到 n

如果 a_i 大于 max 则

把a_i 赋值给 max

最后返回 max

显然这个算法的运行时间为O(n)

再来看一个线性时间的例子

给定两个排好序的序列

A = a_1,a_2,…,a_n 和 B= b_1,b_2,…,b_n

把它们并归为一个有序的整体

第一步初始化i=1,j=1

第二步当A,B都非空时

反复进行如下操作

如果 a_i≤b_j 则将a_i加入输出序列

并且令i增加1

否则将b_j加入输出序列

并且令j增加1

第三步将A,B中仍旧非空的序列

加入输出序列的最后

最后返回输出序列

对于这个算法我们有

并归两个规模为n的序列

需要花费O(n)的时间

在每次比较之后

输出序列的长度增加1

至多进行2n次操作

故算法的运行时间为O(n)

O(n log n)的运行时间

经常出现在分治算法中

对于排序问题

并归排序和堆排序

是执行 O(n log n)次比较的排序算法

最大空间隔问题

给定n个到达服务器时间为

x_1,x_2,…,x_n,的文本副本

则最大的没有文本副本到达的

时间区间是多少

对到达时间进行排序

然后按顺序扫描

并记录下当前的最大时间间隔

在O(n log n) 的时间解决了这个问题

O(n^2)可以枚举所有的元素对

考虑最近点对问题

给定平面中的n个点 (x_1,y_1),…,(x_n,y_n)

找到最接近的一对点

我们可以计算所有的点对之间的距离

然后得到最近的点对

在O(n^2)的时间求解这个问题

第一步将(x_1-x_2)^2 +(y_1-y_2)^2 赋值给 min

第二步从i=1到n循环

从j=i+1到n循环

令d为 (x_i-x_j)^2 +(y_i-y_j)^2

如果d小于min 则令min为d

对于最近点对问题

Ω(n^2)看起来是不可避免的

但这只是错觉

我们在后面的章节

将给出O(n logn)的算法

立方的时间O(n^3)可以枚举所有的三元组

考虑集合不相交问题

给定n个集合 S_1,…,S_n

每一个都是1,2,..,n的一个子集

是否有一对集合是不相交的

下面给出一个O(n^3)的算法

检查任意一对集合

判断它们是否相交

对于每个集合S_i

对于每个其他的集合S_j

对于S_i中的元素p

判断p是否属于S_j

如果S_i中没有元素属于S_j

则返回S_i和S_j是不交的

我们再给一个指数时间算法的例子

独立集问题

给定一个图

求这个图的最大独立集

独立集为图中节点的子集

其中任意的两个节点没有边相连

我们可以枚举图中节点的所有子集

共有2^n个

再逐一检查点集中任意两点间

是否有边相连

需要O(n^2)的时间

因此算法的运行时间为O(n^2 2^n)

算法设计与分析课程列表：

1 Introduction of Algorithm

-1.1 Introduction

--Introduction

-1.2 A First Problem: Stable Matching

--A First Problem: Stable Matching

-1.3 Gale-Shapley Algorithm

--Gale-Shapley Algorithm

-1.4 Understanding Gale-Shapley Algorithm

--Understanding Gale-Shapley Algorithm

-Homework1

-Lecture note 1

--Lecture note 1 Introduction of Algorithm

2 Basics of Algorithm Analysis

-2.1 Computational Tractability

--Computational Tractability

-2.2 Asymptotic Order of Growth

--Asymptotic Order of Growth

-2.3 A Survey of Common Running Times

--A Survey of Common Running Times

-Homework2

-Lecture note 2

--Lecture note 2 Basics of Algorithm Analysis

3 Graph

-3.1 Basic Definitions and Applications

--Basic Definitions and Applications

-3.2 Graph Traversal

--Graph Traversal

-3.3 Testing Bipartiteness

--Testing Bipartiteness

-3.4 Connectivity in Directed Graphs

--Connectivity in Directed Graphs

-3.5 DAG and Topological Ordering

--DAG and Topological Ordering

-Homework3

-Lecture note 3

--Lecture note 3 Graph

4 Greedy Algorithms

-4.1 Coin Changing

--Coin Changing

-4.2 Interval Scheduling

--Interval Scheduling

-4.3 Interval Partitioning

--Interval Partitioning

-4.4 Scheduling to Minimize Lateness

--Scheduling to Minimize Lateness

-4.5 Optimal Caching

--Optimal Caching

-4.6 Shortest Paths in a Graph

--Shortest Paths in a Graph

-4.7 Minimum Spanning Tree

--Minimum Spanning Tree

-4.8 Correctness of Algorithms

--Correctness of Algorithms

-4.9 Clustering

--Clustering

-Homework4

-Lecture note 4

--Lecture note 4 Greedy Algorithms

5 Divide and Conquer

-5.1 Mergesort

--Mergesort

-5.2 Counting Inversions

--Counting Inversions

-5.3 Closest Pair of Points

--Closest Pair of Points

-5.4 Integer Multiplication

--Integer Multiplication

-5.5 Matrix Multiplication

--Video

-5.6 Convolution and FFT

--Convolution and FFT

-5.7 FFT

--FFT

-5.8 Inverse DFT

--Inverse DFT

-Homework5

-Lecture note 5

--Lecture note 5 Divide and Conquer

6 Dynamic Programming

-6.1 Weighted Interval Scheduling

--Weighted Interval Scheduling

-6.2 Segmented Least Squares

--Segmented Least Squares

-6.3 Knapsack Problem

--Knapsack Problem

-6.4 RNA Secondary Structure

--RNA Secondary Structure

-6.5 Sequence Alignment

--Sequence Alignment

-6.6 Shortest Paths

--Shortest Paths

-Homework6

-Lecture note 6

--Lecture note 6 Dynamic Programming

7 Network Flow

-7.1 Flows and Cuts

--Flows and Cuts

-7.2 Minimum Cut and Maximum Flow

--Minimum Cut and Maximum Flow

-7.3 Ford-Fulkerson Algorithm

--Ford-Fulkerson Algorithm

-7.4 Choosing Good Augmenting Paths

--Choosing Good Augmenting Paths

-7.5 Bipartite Matching

--Bipartite Matching

-Homework7

-Lecture note 7

--Lecture note 7 Network Flow

8 NP and Computational Intractability

-8.1 Polynomial-Time Reductions

--Polynomial-Time Reductions

-8.2 Basic Reduction Strategies I

--Basic Reduction Strategies I

-8.3 Basic Reduction Strategies II

--Basic Reduction Strategies II

-8.4 Definition of NP

--Definition of NP

-8.5 Problems in NP

--Problems in NP

-8.6 NP-Completeness

--NP-Completeness

-8.7 Sequencing Problems

--Sequencing Problems

-8.8 Numerical Problems

--Numerical Problems

-8.9 co-NP and the Asymmetry of NP

--co-NP and the Asymmetry of NP

-Homework8

-Lecture note 8

--Lecture note 8 NP and Computational Intractability

9 Approximation Algorithms

-9.1 Load Balancing

--Load Balancing

-9.2 Center Selection

--Center Selection

-9.3 The Pricing Method: Vertex Cover

--The Pricing Method: Vertex Cover

-9.4 LP Rounding: Vertex Cover

--LP Rounding: Vertex Cover

-9.5 Knapsack Problem

--Knapsack Problem

-Homework9

-Lecture note 9

--Lecture note 9 Approximation Algorithms

10 Local Search

-10.1 Landscape of an Optimization Problem

--Landscape of an Optimization Problem

-10.2 Maximum Cut

--Maximum Cut

-10.3 Nash Equilibria

--Nash Equilibria

-10.4 Price of Stability

--Price of Stability

-Homework10

-Lecture note 10

--Lecture note 10 Local Search

11 Randomized Algorithms

-11.1 Contention Resolution

--Contention Resolution

-11.2 Linearity of Expectation

--Linearity of Expectation

-11.3 MAX 3-SAT

--MAX 3-SAT

-11.4 Chernoff Bounds

--Chernoff Bounds

-Homework11

-Lecture note 11

--Lecture note 11 Randomized Algorithms

Exam

-Exam

A Survey of Common Running Times在线视频