- 浏览: 442740 次
- 性别:
- 来自: 深圳
文章分类
- 全部博客 (158)
- J2SE (15)
- c/c++ (17)
- linux & ubuntu (20)
- js (18)
- algorithm (21)
- android (1)
- software (3)
- svn (1)
- db (6)
- other (19)
- css (5)
- go (1)
- html 5 (3)
- computer science (1)
- php (3)
- 创业 (8)
- EJB & jboss (1)
- TDD (1)
- jsp & servlet (2)
- http, tcp & ip (2)
- hibernate (1)
- json (1)
- 乐 (2)
- ps (2)
- netbeans (1)
- extjs (2)
- eclipse (4)
- 项目管理 (1)
- varnish (2)
- study abroad (1)
- python (1)
- erlang (1)
- math (1)
- shell (1)
- assembly (4)
- lucene (1)
- web (1)
- http (1)
- tcp & ip (1)
最新评论
-
yiguxianyun:
...
css li 不换行 -
stdayong:
...
netbeans 中使用 maven -
程序猿_星:
为啥会中文乱码啊
servlet 以 gzip 格式返回数据 -
huanhuan519:
感谢分享~
gdb 调试工具 -
heyl1234:
写过些js,对css还不熟。谢谢~
css li 不换行
Medians and Order Statistics
------
概述
Order Statistics:
次序统计,即 找出 n 个数中 排在 第 i 位 的那个数,记为 ith
Medians:
中位数,排在中间的数,
------
Medians 的取值
假设所有的数都不相同,则:
n = odd 时,只有1个 中间数,i = (n+1)/2,
n = even 时,有2个 中间数,i = n/2 和 i = n/2 + 1,
可以合并为:
i =
lower((n + 1)/2),
upper((n + 1)/2),
对于 odd 2者相同,对于 even 2者不同,
------
最大 & 最小 值
通过 n-1 次比较可以找出 最大 或 最小值,
如果要同时找2者,则可以合并一下,让比较次数小于 2*(n-1),因为如果一个数比另1个数小,则该数必定不是 最大值,反之亦然,
------
次序查找 - 每次分割2组 实现
概述:
通过 分隔函数实现 查找,
效率:
时间复杂度: 预期效率是 O(n)
空间复杂度: O(n)
思路:
基于 quicksort 改造,但每次只取其中的一半,从而效率降低到 O(n),
分隔函数的逻辑:
* 取分隔值,
* 如果分隔值就是目标值,则 ok
* 否则 将数组分隔为 左右2个,
* 判断目标数在哪个数组内,保留那个数组,对其循环调用分隔函数
*
时间复杂度 证明:
略,看 <算法导论> chp9.2
------
次序查找 - 每组5个分割 实现
较为复杂,最差情况下 时间复杂度为 O(n),
参考:<算法导论> chp9.3
------
例子:
(顺序号 查找 - 每次分割2组 实现)
* js(order_statistic.js)
* html
*
------
------
概述
Order Statistics:
次序统计,即 找出 n 个数中 排在 第 i 位 的那个数,记为 ith
Medians:
中位数,排在中间的数,
------
Medians 的取值
假设所有的数都不相同,则:
n = odd 时,只有1个 中间数,i = (n+1)/2,
n = even 时,有2个 中间数,i = n/2 和 i = n/2 + 1,
可以合并为:
i =
lower((n + 1)/2),
upper((n + 1)/2),
对于 odd 2者相同,对于 even 2者不同,
------
最大 & 最小 值
通过 n-1 次比较可以找出 最大 或 最小值,
如果要同时找2者,则可以合并一下,让比较次数小于 2*(n-1),因为如果一个数比另1个数小,则该数必定不是 最大值,反之亦然,
------
次序查找 - 每次分割2组 实现
概述:
通过 分隔函数实现 查找,
效率:
时间复杂度: 预期效率是 O(n)
空间复杂度: O(n)
思路:
基于 quicksort 改造,但每次只取其中的一半,从而效率降低到 O(n),
分隔函数的逻辑:
* 取分隔值,
* 如果分隔值就是目标值,则 ok
* 否则 将数组分隔为 左右2个,
* 判断目标数在哪个数组内,保留那个数组,对其循环调用分隔函数
*
时间复杂度 证明:
略,看 <算法导论> chp9.2
------
次序查找 - 每组5个分割 实现
较为复杂,最差情况下 时间复杂度为 O(n),
参考:<算法导论> chp9.3
------
例子:
(顺序号 查找 - 每次分割2组 实现)
* js(order_statistic.js)
var arr_order_statistic = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ]; /** * <p> * order statistic , 找出排序为 i 的值 * </p> * <b>思路:</b><br /> * 基于 quicksort 改造,但每次只取其中的一半,从而效率降低到 O(n),<br /> * * <pre> * 分隔函数的逻辑: * 取分隔值, * 如果分隔值就是目标值,则 ok * 否则 将数组分隔为 左右2个, * 判断目标数在哪个数组内,保留那个数组,对其循环调用分隔函数 * </pre> * * <b>时间复杂度:</b>O(n)<br /> * <b>空间复杂度:</b>O(n)<br /> * * @author kuchaguangjie * @date 2011年1月3日 * @return */ function OrderStatistic(inputArr) { this.inputArr = inputArr; } /** * 单次分隔 * * @param arr * @param i * 在 arr 中的排序,从 0 开始 * @return 存有目标值的子数组 或 目标值 */ OrderStatistic.prototype.partitionSingle = function(arr, i) { if (arr.length <= 1) { // length == 1 的情况,length == 0 应该在上层函数中排除掉, return new OrderStaticResult(true, undefined, undefined, arr[0]); } var partLeftArr = []; var partRightArr = []; var partMiddle = arr[arr.length - 1]; // 最后1个元素,用作分隔值 for ( var x = 0; x < arr.length - 1; x++) { if (arr[x] <= partMiddle) { partLeftArr[partLeftArr.length] = arr[x]; } else { partRightArr[partRightArr.length] = arr[x]; } } if (partLeftArr.length == i) { // 分隔值 即是 目标值 return new OrderStaticResult(true, undefined, undefined, partMiddle); } else if (partLeftArr.length > i) { // 目标值 在 左子数组 return new OrderStaticResult(false, partLeftArr, i); } else { // 目标值 在 右子数组 i -= (partLeftArr.length + 1); // 调整 i return new OrderStaticResult(false, partRightArr, i); } }; /** * 分隔函数,直到找到目标值为之 * * @param i * @return */ OrderStatistic.prototype.partition = function(i) { var arr = this.inputArr; var osr; while (true) { osr = this.partitionSingle(arr, i); if (osr.ok) { return osr.v; } else { arr = osr.subArr; i = osr.i; } } }; /** * 根据 排序号 找到数 * * @param order * 排序号,从 1 开始 * @return */ OrderStatistic.prototype.getByOrder = function(order) { if (this.inputArr.length == 0 || this.inputArr.length < order) { alert('输入有误!'); } else { var i = order - 1; // index 从 0 开始,而顺序号是从 1 开始,这里做调整 return this.partition(i); } }; /** * 单次 分隔计算 后的返回值 * * @param ok * boolean 值,表示 是否已找到 * @param subArr * 目标值所在的子数组,当 ok = false 时,采用此数组 * @param i * 目标值在的子数组中的排序,从 0 开始,当 ok = false 时,采用此值 * @param v * 目标值,当 ok = true 时,才用此值 * @return */ function OrderStaticResult(ok, subArr, i, v) { this.ok = ok; this.subArr = subArr; this.i = i; this.v = v; }
* html
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html> <head> <meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /> <script type="text/javascript" src="js/order_statistic.js"></script> </head> <body> <input type="button" value="order statistic" onclick="var i = 6;alert(arr_order_statistic + ' 中,\n排在第'+ i +'位的是: '+ new OrderStatistic(arr_order_statistic).getByOrder(i));" /> </body> </html>
*
------
发表评论
-
c - linkedlist
2012-05-10 14:52 1079c - linkedlist store ordere ... -
c - word counter (binary-tree)
2012-05-09 14:17 1723c - word counter (binary-tree) ... -
random select
2011-08-28 01:00 1203random select problem: ... -
sparse data structure - matrix
2011-08-18 20:03 1077sparse data structure sp ... -
max sub_sequence - c
2011-08-10 01:02 1072max sub_sequence - c /* ... -
binary search - c
2011-08-06 12:07 1089binary search - c (simple) ... -
bit_array - simple use
2011-05-28 23:47 1005bit array,use less memory to de ... -
linkedlist - java 简单实现
2011-02-11 21:29 1592linked list 链表, - ... -
queue (用 java 简单实现)
2011-02-03 01:45 4047queue ------ 结构 线性存 ... -
counting sort
2011-01-02 20:36 1562counting sort ------ counting ... -
quick sort
2011-01-01 20:26 1188quicksort ------ quicksort ove ... -
priority queue
2010-12-22 00:11 2268priority queue priority queue ... -
heap sort
2010-12-18 19:09 1205heapsort ------ heap 数据结构 hea ... -
merge sort
2010-12-01 23:37 1148merge sort 合并排序 ------ merge ... -
insertion sort
2010-10-28 00:21 1043insertion sort ------ insertio ... -
z 字型 读取 矩阵
2010-10-23 16:50 2188以 z 字型 读取 矩阵, ... -
排序算法:求 长度为 n的 数组中,最大的 m个数
2010-08-31 10:16 2626排序:数组 length=m,从其中中取出最大的 n 数字,n ... -
已排序数组 a,求其元素的绝对值 共有多少个不同的值
2010-08-29 20:41 1598已排序数组 a,求其元素的绝对值 共有多少个不同的值? ... -
binary search
2010-08-29 19:35 966binary search in sorted array: ... -
An Introduction to Algorithm 2nd 's contents
2010-08-11 23:02 1184算法导论(2nd) 结构 * <Introductio ...
相关推荐
Chapter 9 - Medians and Order Statistics Part III - Data Structures Chapter 10 - Elementary Data Structures Chapter 11 - Hash Tables Chapter 12 - Binary Search Trees Chapter 13 - Red-Black ...
Chapter 9 - Medians and Order Statistics Part III - Data Structures Chapter 10 - Elementary Data Structures Chapter 11 - Hash Tables Chapter 12 - Binary Search Trees Chapter 13 - Red-Black ...
Chapter 9 - Medians and Order Statistics Part III - Data Structures Chapter 10 - Elementary Data Structures Chapter 11 - Hash Tables Chapter 12 - Binary Search Trees Chapter 13 - Red-Black ...
Chapter 9 - Medians and Order Statistics Part III - Data Structures Chapter 10 - Elementary Data Structures Chapter 11 - Hash Tables Chapter 12 - Binary Search Trees Chapter 13 - Red-Black ...
Chapter 9 - Medians and Order Statistics Part III - Data Structures Chapter 10 - Elementary Data Structures Chapter 11 - Hash Tables Chapter 12 - Binary Search Trees Chapter 13 - Red-Black ...
9. **中位数和有序统计(Medians and Order Statistics)**:ch9 Medians and Order Statistics.pdf 解释了如何在未排序的数据中找到中位数和其他特定位置的元素,这对于处理大数据集特别有用。 这些主题覆盖了算法...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十二章 ...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十二章 二叉...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十二章 二叉...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十...
6. 中位数和顺序统计(Medians and Order Statistics):讨论了线性时间选择算法和最坏情况下的线性选择算法,这部分内容对于理解如何在数据集中找到关键的中位数等统计值至关重要。 7. 基本数据结构(Elementary ...
Chapter 9: Medians and Order Statistics Lecture Notes 9-1 Solutions 9-10 Chapter 11: Hash Tables Lecture Notes 11-1 Solutions 11-16 Chapter 12: Binary Search Trees Lecture Notes 12-1 Solutions 12-15 ...
第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十...
本文是对选择算法或者称为“中位数中位数”算法的详细分析,该算法是文本中未详尽阐述的。首先,我们要明确算法的几个关键点:S表示要从中选择的n个不同元素的集合,g为向下取整的n/5,代表分组的数量,m是算法找到...