分而治之
例子：求解股市最大收益
P38
思路
? 容易犯的错误
? 使用穷丼两两组合的方法
转化问题
分而治之的思路
伪代码
算法分析
《算法导论》第42页
矩阵乘法的Strassen算法
? 普通矩阵乘法算法复杂度为n立方级别
? 分而治之的思路，可以达到n平方级别
P43
伪代码
分治法算法复杂度推算
? 从递归式子推算复杂度
? 代入法
? 递归树
? 主方法与主定理
用递归树方法求解递归式
p50
用主方法求解递归式
p53
堆排序（heapsort）
? 二叉堆
最大堆和最小堆
? 最大堆：应用于堆排序
? 最小堆：应用于构造优先队列
堆排序过程
MAX-HEAPIFY过程
? 要解决的问题：当根节点（相对）的左子树和右子树都是最大堆时，怎样把堆变成最
大堆？
节点逐级下降示意图
把堆变成最大堆
? 利用分而治之和递归的标准思路
堆排序
算法分析
? 复杂度O（nlgn）
? 复杂度要低于插入排序，与归并排序相若
? 具有空间原址性，即可以在原数组内进行排序而不需要额外空间，与插入排序相若，
优于归并排序
快速排序的算法思想
伪代码
过程图解
算法分析
? 最坏情况
? 最好情况
? 平均情况O(nlgn)
习题 1：归并排序（数组上的分治）
代码
例子：求解股市最大收益
P38
思路
? 容易犯的错误
? 使用穷丼两两组合的方法
转化问题
分而治之的思路
伪代码
算法分析
矩阵乘法的Strassen算法
? 普通矩阵乘法算法复杂度为n立方级别
? 分而治之的思路，可以达到n平方级别
P43
伪代码
分治法算法复杂度推算
? 代入法
? 递归树
? 主方法与主定理
用递归树方法求解递归式
p50
用主方法求解递归式
p53
堆排序（heapsort）
最大堆和最小堆
? 最大堆：应用于堆排序
? 最小堆：应用于构造优先队列
堆排序过程
MAX-HEAPIFY过程
大堆？
节点逐级下降示意图
把堆变成最大堆
堆排序
算法分析
? 复杂度要低于插入排序，与归并排序相若
? 具有空间原址性，即可以在原数组内进行排序而不需要额外空间，与插入排序相若，
优于归并排序
快速排序的算法思想
伪代码
过程图解
算法分析
? 最坏情况
? 最好情况
? 平均情况O(nlgn)
习题 1：归并排序（数组上的分治）
代码
点击(此处)折叠或打开
-
#include <iostream>
-
#include <cstdio>
-
using namespace std;
-
#define MAXN 70000
-
int a[MAXN];
-
int la[MAXN], ra[MAXN];
-
long long cnt; /* 逆序对数目 */
-
void merge( int l, int m, int r ) /* l 左边界，m中值，r右边界 */
-
{
-
int p1 = 0, p2 = 0, j, k;
-
for ( int i = l; i <= m; i++ )
-
la[p1++] = a[i]; /* 初始化la数组 */
-
for ( int i = m + 1; i <= r; i++ )
-
ra[p2++] = a[i]; /* 初始化ra数组 */
-
la[p1] = ra[p2] = 0x3f3f3f3f;
-
j = k = 0;
-
for ( int i = l; i <= r; i++ )
-
{
-
if ( la[j] <= ra[k] )
-
a[i] = la[j++];
-
else{
-
a[i] = ra[k++];
-
cnt += p1 - j;
-
}
-
}
-
}
-
-
-
void mergeSort( int l, int r )
-
{
-
if ( l >= r )
-
return;
-
int m = (l + r) >> 1;
-
mergeSort( l, m );
-
mergeSort( m + 1, r );
-
merge( l, m, r );
-
}
-
-
-
int main()
-
{
-
int n;
-
while ( ~scanf( \"%d\", &n ) )
-
{
-
cnt = 0;
-
for ( int i = 0; i < n; i++ )
-
scanf( \"%d\", &a[i] );
-
mergeSort( 0, n - 1 );
-
printf( \"%lld\\n\", cnt );
-
}
-
return(0);
- }
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/28673014/viewspace-1618761/ ，如需转载，请注明出处，否则将追究法律责任。
下一篇：
在R中使用SQL操作数据框
请登录后发表评论
登录
全部评论
