Inverse DFT慕课视频播放-算法设计与分析-MOOC慕课视频教程-柠檬大学

为了实现相反的转换

我们需要反向傅里叶变换

我们的目标是给定一个n-1次多项式

在n次单位根ω^0, ω^1, …, ω^n-1处的值

y_0, y_1 ... , y_n-1

写出它的系数形式

由我们刚才所得到的矩阵关系

我们可以得到反向傅里叶变换关系

这里的系数矩阵是傅里叶矩阵的逆

经过代数推导

我们可以显示的写出傅里叶矩阵的逆

我们看到它和傅里叶矩阵是很相似的

只不过 ω改为ω^-1

然后最后的结果要除以n

我们把FFT算法进行相应的修改

得到了反向FFT

这里注意

FFT算法中ω改为了ω^-1

最后的结果还要除以n

我们的结论是

反向FFT算法

给定n-1次多项式

在n次单位根处的值

它在O(nlogn)的时间内计算出它的系数形式

由上面的分析我们有

T(2n)=2T(n)+O(n)⇒T(n)=O(nlogn)

这样我们实现了

系数形式和点值形式的双向转换

所需的时间都是O(nlogn)

现在我们给定两个系数形式的n-1次多项式

我们来看一下

如何用FFT算法

快速实现它们的乘积

它们的乘积是2n-2次多项式

我们需要知道2n-1个点处的值

这可以用FFT在O(nlogn)的时间来实现

对于点值形式的多项式乘积

可以在O(n)的时间内实现

最后我们再用反向FFT

把点值形式的乘积多项式

转换为系数形式

所需的时间也是O(nlogn)

总共的运行时间也可以被O(nlogn)所控制

我们再回到整数乘法

给定两个n位整数

a=a_n-1…a_1a_0

b=b_n-1…b_1b_0

计算c=a×b

我们可以采用卷积算法

分别以a_n-1…a_1a_0和b_n-1…b_1b_0为系数

定义两个n-1次多项式A(x)和B(x)

我们发现a恰好为A(2)的值以及b=B(2)

我们可以通过计算C(x)=A(x)×B(x)

得到乘积多项式

然后通过计算C(2)来得到a×b

看起来好像有些大材小用

而且刚才我们得到O(nlogn)的运行时间

是把一次算数运算作为一次基本运算

而对于整数乘法来说

一次位运算为一次基本运算

但是由于问题的特殊性

以及复数运算的特点

在71年基于FFT

得到了O(nlognloglogn)次位运算

实现了整数乘法

随着算法研究的发展

近年来又有了提高的结果

对于FFT算法以及分治算法的介绍

就到这里

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

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

Inverse DFT在线视频

Inverse DFT

Inverse DFT课程教案、知识点、字幕