分治法求最大、最小元算法_liangyuan040

http://blog.sina.com.cn/u/1860836290

首页博文目录关于我

个人资料

微博

加好友发纸条

写留言加关注

博客等级：
博客积分：

博客访问：
关注人气：
获赠金笔：0支
赠出金笔：0支
荣誉徽章：

正文字体大小：大中小

分治法求最大、最小元算法

(2010-01-08 09:16:33)

标签：

杂谈

分类： MSN搬家

当n=2时，一次比较就可以找出两个数据元素的最大元和最小元。当n>2时，可以把n个数据元素分为大致相等的两半，一半有n/2个数据元素，而另一半有n/2个数据元素。先分别找出各自组中的最大元和最小元，然后将两个最大元进行比较，就可得n个元素的最大元；将两个最小元进行比较，就可得n个元素的最小元。

求最大、最小元算法的时间复杂度（比较次数）下界是多少？分治算法在什么情况下可以达到下界？

答：在规模为n的数据元素集合中找出最大元和最小元，至少需要3n/2-2次比较，即3n/2-2是找最大最小元算法的下界。当n=2k,或当n≠2k时，若n是若干2的整数幂之和，（e.g. 42=32+8+2），

则算法的时间复杂度仍可达到3n/2-2。

程序源码如下：
#include<iostream>
using namespace std;
typedef int ElemType;

#define LIST_INIT_SIZE 100
#define LIST_INCREMENT 10

typedef struct{
    ElemType *elem;
    int length;
    int listsize;
}SqList;

//定义一个顺序表
void InitList_Sq(SqList &L,int n){
    L.elem = new ElemType[LIST_INIT_SIZE];
    int i;
    for(i=1;i<=n;i++){
        cin>>L.elem[i];
    }
}

//输出该顺序表
void outPut(SqList L,int n){
    for(int i=1;i<=n;i++){
        cout<<L.elem[i]<<" ";
    }
}

//求最小值
void selectMin(SqList &L,int n){
    for(int i=1,k=1;i<=n;i=i+2,k++){
        if(L.elem[i]>L.elem[i+1])
            L.elem[k]=L.elem[i+1];
        else L.elem[k]=L.elem[i];
    }
    while(n>=2){
        n=n/2;
        selectMin(L,n);
    }
}

//求最大值
void selectMax(SqList &L,int n){
    for(int i=1,k=1;i<=n;i=i+2,k++){
        if(L.elem[i]<L.elem[i+1])
            L.elem[k]=L.elem[i+1];
        else L.elem[k]=L.elem[i];
    }
    while(n>=2){
        n=n/2;
        selectMax(L,n);
    }
}

void main(){
    SqList L;
    cout<<"请输入8个数字求最小值："<<endl;
    InitList_Sq(L,8);
    outPut(L,8);
    cout<<endl;
    selectMin(L,8);
    cout<<"最小值为："<<L.elem[1]<<endl;

    cout<<"请输入8个数字求最大值："<<endl;
    InitList_Sq(L,8);
    outPut(L,8);
    cout<<endl;
    selectMax(L,8);
    cout<<"最大值为："<<L.elem[1]<<endl;
}

阅读┊ 收藏 ┊ 喜欢 ▼ ┊打印┊举报/Report

前一篇：比尔.盖茨的11条忠告

后一篇：快速排序

新浪BLOG意见反馈留言板　欢迎批评指正