O(N)+x=2*O(N/2)+2*x
a*O(N)+x=a*(2*O(N/2)+x)+x=2*a *O(N/2)+(a+1)*x 由此可知,时间复杂度可达到O(n);
3.分治策略一定导致递归吗?如果是,请解释原因。如果不是,给出一个不包含递归的分治例子,并阐述这种分治和包含递归的分治的主要不同。
不一定导致递归。
如非递归的二叉树中序遍历。
这种分治方法与递归的二叉树中序遍历主要区别是:应用了栈这个数据结构。
4. 对于待排序序列(5, 3, 1, 9),分别画出归并排序和快速排序的递归运行轨迹。
归并排序:
第一趟:(5,3)(1,9); 第二趟:(3,5,1,9); 第三趟:(1,3,5,9);
快速排序:
第一趟:5( ,3,1,9);//5为哨兵,比较9和5 第二趟:5(1,3, ,9);//比较1和5,将1挪到相应位置; 第三趟:5(1,3, ,9);//比较3和5; 第四趟:(1,3,5,9);
5. 设计分治算法求一个数组中的最大元素,并分析时间性能。
//简单的分治问题
//将数组均衡的分为“前”,“后”两部分
//分别求出这两部分最大值,然后再比较这两个最大值
#includeusing namespace std;
extern const int n=6;//声明 int main() { int a[n]={0,6,1,2,3,5};//初始化 int mid=n; int num_max1=0,num_max2=0; for(int i=0;i<=n;++i)//前半部分 { if(a[i]>num_max1) num_max1=a[i];
} for(int j=n+1;jnum_max2) num_max2=a[j]; } if(num_max1>=num_max2) cout<
cout<
时间复杂度:O(n)
6. 设计分治算法,实现将数组A[n]中所有元素循环左移k个位置, 要求时间复杂性为O(n),空间复杂性为O(1)。例如,对abcdefgh循环左移3位得到defghabc。
//采用分治法
//将数组分为0-k-1和k-n-1两块 //将这两块分别左移 //然后再合并左移
#include using namespace std;
void LeftReverse(char *a, int begin, int end) {
for(int i=0;i
int temp=a[begin+i]; a[begin+i]=a[end-i]; a[end-i]=temp; } }
void Converse(char *a,int n,int k) {
LeftReverse(a, 0, k+1); LeftReverse(a, k, n+1);
LeftReverse(a, 0, n-1); for(int i=0;iint main() {
char a[7]={'a','b','c','d','e','f','g'}; Converse(a,7,3);
return 0; }
7. 设计递归算法生成n个元素的所有排列对象。
#include using namespace std;
int data[100];
//在m个数中输出n个排列数(n<=m) void DPpl(int num,int m,int n,int depth) {
if(depth==n) {
for(int i=0;ifor(int j=0;jif((num&(1
DPpl(0,5,1,0);
DPpl(0,5,2,0); DPpl(0,5,3,0); DPpl(0,5,4,0); DPpl(0,5,5,0);
return 0; }
8. 设计分治算法求解一维空间上n个点的最近对问题。
参见4.4.1最近对问题的算法分析及算法实现
9. 在有序序列(r1, r2, ?, rn)中,存在序号i(1≤i≤n),使得ri=i。请设计一个分治算法找到这个元素,要求算法在最坏情况下的时间性能为O(log2n)。
//在有序数组中
//采用二分法查找符合条件的元素
#includeusing namespace std;
void Findnum(int *a,int n) {
int low=0; int high=n-1;
while(low<=high) {
int mid=(low+high)/2; if(a[mid]==mid) { cout