随笔 - 70  文章 - 160  trackbacks - 0

公告:
知识共享许可协议
本博客采用知识共享署名 2.5 中国大陆许可协议进行许可。本博客版权归作者所有,欢迎转载,但未经作者同意不得随机删除文章任何内容,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。 具体操作方式可参考此处。如您有任何疑问或者授权方面的协商,请给我留言。

常用链接

留言簿(8)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 177877
  • 排名 - 147

最新评论

阅读排行榜

评论排行榜

建议先看看前言:http://www.cppblog.com/tanky-woo/archive/2011/04/09/143794.html

这一章的内容很简单,基本都是一些概念。

第i个顺序统计量:在一个由n个元素组成的集合中,第i个顺序统计量(order statistic)是该集合中第i小的元素。

最小值是第1个顺序统计量(i=1)

最大值是第n个顺序统计量(i=n)

中位数:一个中位数(median)是它所在集合的“中点元素”,当n为奇数时,i=(n+1)/2,当n为偶数是,中位数总是出现在1 (下中位数)和2 (上中位数)。

找最大值/最小值问题,通过比较n-1次可以得出结果。

MINIMUM(A)
1  minA[1]
2  for i ← 2 to length[A]
3         do if min > A[i]
4                then minA[i]
5  return min

如果要同时找出最大值和最小值,则比较次数最少并不是2*n-2,而是3 ,我们可以将一对元素比较,然后把较大者于max比较,较小者与min比较,这样就只需要3

如果是一般的选择问题,即找出一段序列第i小的数,看起来要比找最大值或最小值要麻烦,其实两种问题的渐进时间都是4

首先看看这个强悍的伪代码:

RANDOMIZED-SELECT(A, p, r, i)
1  if p = r
2      then return A[p]
3  q ← RANDOMIZED-PARTITION(A, p, r)
4  kq - p + 1
5  if i = k          ▹ the pivot value is the answer
6      then return A[q]
7  elseif i < k
8      then return RANDOMIZED-SELECT(A, p, q - 1, i)
9  else return RANDOMIZED-SELECT(A, q + 1, r, i - k)

这个算法利用了随机化的Partition算法,这个实在第七章的随机化快排中讲到:http://www.wutianqi.com/?p=2368,不记得的可以先复习下前面的快排。

这个随机化的选择算法返回数组A[p..r]中第i小的元素。

具体实现如下:

 1 /*
 2 Author: Tanky Woo
 3 Blog:   www.WuTianQi.com
 4 About:  《算法导论》第9章 查找序列第i小的数字
 5 */
 6  
 7 #include <iostream>
 8 #include <cstdlib>
 9 using namespace std;
10  
11 int Partition(int *arr, int beg, int end)
12 {
13     int sentinel = arr[end];
14     int i = beg-1;
15     for(int j=beg; j<=end-1++j)
16     {
17         if(arr[j] <= sentinel)
18         {
19             i++;
20             swap(arr[i], arr[j]);
21         }
22     }
23     swap(arr[i+1], arr[end]);
24  
25     return i+1;
26 }
27  
28 int RandomPartition(int *arr, int beg, int end)
29 {
30     int i = beg + rand() % (end-beg+1);
31     swap(arr[i], arr[end]);
32     return Partition(arr, beg, end);
33 }
34  
35  
36 int RandomSelect(int *a, int p, int r, int i)
37 {
38     if(p == r)
39         return a[p];
40     int q = Partition(a, p, r);
41     int k = q-p+1;
42     if(i == k)
43         return a[q];
44     else if(i < k)
45         return RandomSelect(a, p, q-1, i);
46     else
47         return RandomSelect(a, q+1, r, i-k);
48 }
49  
50 int main()  
51 {  
52     int a[] = {08910021528332763};  
53     int num = 9;   
54     int ith;
55     cout << "序列为: ";
56     for(int i=1; i<=num; ++i)  
57         cout << a[i] << " ";
58     cout << endl;
59     ith = RandomSelect(a, 1, num, 2);
60     cout << "序列中第2小的数字是: " << ith << endl;
61     getchar();
62  
63     return 0;  
64 }

结果如图:
5

在(89, 100, 21, 5, 2, 8, 33, 27, 63)中查找第二小的数字是5. 

该算法的平均情况性能较好,并且又是随机化的,所有没有哪一种特别的输入会导致最坏情况发生。



在我独立博客上的原文:http://www.wutianqi.com/?p=2395
欢迎大家互相学习,互相探讨。
posted on 2011-04-26 13:00 Tanky Woo 阅读(1565) 评论(1)  编辑 收藏 引用

FeedBack:
# re: 《算法导论》学习总结 — 9.第九章 中位数和顺序统计学 2012-11-24 17:20 
对于效果来说则是业绩效果论述目前的没有信息分析的依据在目前来说其实是对于电脑上面的文字不愿意去看,内心总是叹气的一种心理表现,  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理