算法设计与分析复习题(2)

int left(int i) { return 2*i; }

int right(int i) {

return 2*i+1; }

.//返回左节点

//返回右节点;

int iparent(int i) { return i/2; }

void heapify(double a[],int i) {

int l=left(i); int r=right(i); int largest;

if(l<=heapsize &&a[l]>a[i])

largest=l; else largest=i;

if(r<=heapsize&&a[r]>a[largest])

largest=r;

if (largest!=i) { }

double temp=a[i]; a[i]=a[largest]; a[largest]=temp; heapify(a,largest);

}

void build_heap(double a[]) {

heapsize=alength;

for (int i=alength/2;i>=1;i--) heapify(a,i); };

void heapsort(double a[]) {

build_heap(a); int k=0;

cout<=2;i--) { } } int main() {

printf(\k++; if(k==0) cout<

//建立大头堆

//调整大头堆

double a[M]; srand(time(0)); printf(\ for (int i=1;i

heapsort(a);

a[i]=rand()-5000; a[i]+=rand()/10000.0; if(i==0) printf(\else

printf(\

return 0; }

时间复杂度为O(nlogn)，heapify()的时间复杂度为O(logn)

11、 证明O(nlogn)是“比较”排序算法时间复杂性的下界。

这个首先要明确一点，只用到比较的排序算法最低时间复杂度是O(nlogn)，而像桶排这样的只需要O(R)(R为桶的大小)

为了证明只用到比较的排序算法最低时间复杂度是O(nlogn)，首先要引入决策树。 首先决策树是一颗二叉树，每个节点表示元素之间一组可能的排序，它予以京进行的比较相一致，比较的结果是树的边。

先来说明一些二叉树的性质，令T是深度为d的二叉树，则T最多有2^片树叶。 具有L片树叶的二叉树的深度至少是logL。

所以，对n个元素排序的决策树必然有n!片树叶（因为n个数有n!种不同的大小关系），所以决策树的深度至少是log(n!)，即至少需要log(n!)次比较。 而

log(n!)=logn+log(n-1)+log(n-2)+...+log2+log1 >=logn+log(n-1)+log(n-2)+...+log(n/2) >=(n/2)log(n/2) >=(n/2)logn-n/2 =O(nlogn)

所以只用到比较的排序算法最低时间复杂度是O(nlogn)。

12、 编写一个Radix算法对n个相同长度的整数排序。

#include #include #define M 10 using namespace std; queue m; queue r[10];

int radixsort(queue m,int n) {

for(int i=0;i

while(m.size()!=0)

{

int temp=m.front(); m.pop(); if(i==0)

r[temp].push(temp); else

r[temp/(i*10)].push(temp);*/ int temp2=1; for(int k=0;k

temp2*=10;

/* }

}

r[temp/(temp2)].push(temp);

for(int j=0;j<10;j++) { }

while(r[j].size()!=0) { }

int temp=r[j].front(); r[j].pop(); m.push(temp);

cout<

{ }

int temp=m.front(); m.pop();

cout<

return 0;