`

Medians and Order Statistics (次序统计)

阅读更多
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)
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>


*

------

分享到:
评论

相关推荐

    麻省理工算法导论(完整精辟版)

    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 ...

    [麻省理工学院-算法导论](英文版).chm

    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 ...

    算法导论(英文第2版)

    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 ...

    [麻省理工学院-算法导论].Introduction.to. Algorithms,.Second.Edition

    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 ...

    算法导论ppt

    9. **中位数和有序统计(Medians and Order Statistics)**:ch9 Medians and Order Statistics.pdf 解释了如何在未排序的数据中找到中位数和其他特定位置的元素,这对于处理大数据集特别有用。 这些主题覆盖了算法...

    算法导论-第三版(中文).rar

    第九章 中值与顺序统计(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) 第十二章 二叉...

    算法导论Introduction to Algorithms

    第九章 中值与顺序统计(Medians and Order Statistics) 第三部分(Part III) 数据结构(Data Structures) 第十章 基本的数据结构(Elementary Data Structures) 第十一章 散列表(Hash Tables) 第十二章 二叉...

    算法导论Introduction.to.Algorithms,.Second.Edition.part2(英文)

     第九章 中值与顺序统计(Medians and Order Statistics)  第三部分(Part III) 数据结构(Data Structures)  第十章 基本的数据结构(Elementary Data Structures)  第十一章 散列表(Hash Tables)  第十...

    算法导论Introduction.to.Algorithms,.Second.Edition.part1(英文版)

     第九章 中值与顺序统计(Medians and Order Statistics)  第三部分(Part III) 数据结构(Data Structures)  第十章 基本的数据结构(Elementary Data Structures)  第十一章 散列表(Hash Tables)  第十...

    算法导论习题答案

    6. 中位数和顺序统计(Medians and Order Statistics):讨论了线性时间选择算法和最坏情况下的线性选择算法,这部分内容对于理解如何在数据集中找到关键的中位数等统计值至关重要。 7. 基本数据结构(Elementary ...

    算法导论第三版 solution(英文版)

    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)  第十...

    Analysis of Median of Medians Algorithm

    本文是对选择算法或者称为“中位数中位数”算法的详细分析,该算法是文本中未详尽阐述的。首先,我们要明确算法的几个关键点:S表示要从中选择的n个不同元素的集合,g为向下取整的n/5,代表分组的数量,m是算法找到...

Global site tag (gtag.js) - Google Analytics