卷积及其应用

向量计算

给定向量：

• $a=(a_0, a_1, ..., a_{n-1})$

• $b=(b_0, b_1, ..., a_{n-1})$

向量和： $a+b=(a_0+b_0,a_1+b_1,...,a_{n-1}+b_{n-1}$

幂乘问题

输入：$a$为给定实数，$n$为自然数

输出：$a^n$

传统算法思想

顺序相乘 $a^n=(...(((a\quad a)a)a)...)a$

乘法次数：$\varTheta (n)$

基础思想

• 用首元素$x$作划分标准，将输入数组$A$划分成不超过$x$的元素构成的数组$A_L$，大于$x$的元素构成的数组$A_R$。其中，$A_L,A_R$从左到右存放数组$A$的位置。

• 递归地堆子问题$A_L$和$A_R$进行排序，直到子问题规模为$1$时停止。

减少子问题数

依据

分治算法的时间复杂度方程

$W(n) = aW(n/b) + d(n)$

$a$：子问题数，$n/b$：子问题规模，$d(n)$：划分与综合工作量。

算法设计思想

• 将原问题归结为规模为n-1的2个子问题；

• 继续归约，将原问题归结为规模为n-2的4个子问题。继续…，当子问题规模为1时，归约过程截止。

• 从规模1到n-1，陆续组合两个子问题的解。直到规模为n。

• 分析方法：递推方程。

基础思想

分治策略(Divide and Conquer)基本思想：

1. 将原始问题划分或者归结为规模较小的子问题；

2. 递归或迭代求解每个子问题；

3. 将子问题的解综合得到原问题的解。

选择问题

选最大和最小

输入：集合$L$（含$n$个不等的实数）

输出：$L$中的第$i$小的元素

• $i=1$，称为最小元素

• $i=n$，称为最大元素

位置处在中间爱你位置的元素，成为中位元素。

$n$为奇数，中位数唯一，$i=(n+1)/2$。

$n$为偶数，可指定为$i=n/2+1$。

选最大算法：顺序比较，在最坏情况下的时间为$W(n)=n-1$。