# Medians and Order Statistics (order statistics)

2011-01-03  来源：本站原创  分类：Tech  人气：77

Medians and Order Statistics

------
Overview

Order Statistics:
Order statistics, that is ranked the number to find out n bits in the number of i, denoted by ith

Medians:
The median in the middle is the number of

------
Medians values

Assuming all the numbers are not the same, then:
n = odd, only an intermediate number, i = (n +1) / 2,
n = even, there are two middle numbers, i = n / 2 and i = n / 2 + 1,

Can be combined as:
i =
lower ((n + 1) / 2),
upper ((n + 1) / 2),
For the odd 2 are the same as those for even 2 different

------
Maximum & minimum

By n-1 comparisons to find the maximum or minimum value,
If you want to find two persons, you can merge and let the number of comparisons is less than 2 * (n-1), because if a small number of the number than the other one, the number certainly not the maximum, and vice versa,

------
Order to find - each division 2 group achieved

Overview:
Achieved by separating the function to find,

Efficiency:
Complexity: the expected efficiency is O (n)
Space complexity: O (n)

Ideas:
Quicksort-based transformation, but each time taking only half of them, thus reducing efficiency to O (n),

The logic of separating the function:
* Take-separated values,
* If separated value is the target, then ok
* If the array is separated by about 2,
* Determine the number of targets within the array in which to retain the array, separated by their function call loop
*

Time complexity of proof:
Strategy, see <Introduction to Algorithms> chp9.2

------
Order to find - each division to achieve 5

More complex, the worst-case time complexity is O (n),

References: <Introduction to Algorithms> chp9.3

------
Example:

(Sequence number to find - each division 2 group achieved)

* Js (order_statistic.js)

```var arr_order_statistic = [ 78, 13, 6, 177, 26, 90, 288, 45, 62, 83 ];

/**
* <p>
* order statistic ,   I find the value of the order of
* </p>
* <b>  Ideas  :</b><br />
*   Transformation based on quicksort  ,  But each time only to take one of the half, down to the efficiency of   O(n),<br />
*
* <pre>
*   The logic of separating the function  :
*        Separated values obtained  ,
*        If the target value is separated, then   ok
*        Otherwise, the array is separated     About 2  ,
*        Determine the number of targets within the array in which to retain the array  ,  Separate function calls to their circulation
* </pre>
*
* <b>  Time complexity  :</b>O(n)<br />
* <b>  Space complexity  :</b>O(n)<br />
*
* @author kuchaguangjie
* @date 2011  In January  3  Date
* @return
*/
function OrderStatistic(inputArr) {
this.inputArr = inputArr;
}
/**
*   Separated by a single
*
* @param arr
* @param i
*              The order in arr  ,  From 0
* @return   There are sub-array or target     Target
*/
OrderStatistic.prototype.partitionSingle = function(arr, i) {
if (arr.length <= 1) { // length == 1  Situation, length == 0 should be excluded in the upper function  ,
return new OrderStaticResult(true, undefined, undefined, arr[0]);
}
var partLeftArr = [];
var partRightArr = [];
var partMiddle = arr[arr.length - 1]; //   Finally, an element  ,  Separated values for
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) { //   Separated values is     Target
return new OrderStaticResult(true, undefined, undefined, partMiddle);
} else if (partLeftArr.length > i) { //   Target in     Left subarray
return new OrderStaticResult(false, partLeftArr, i);
} else { //   Target in     The right sub-array
i -= (partLeftArr.length + 1); //   Adjustment   i
return new OrderStaticResult(false, partRightArr, i);
}
};
/**
*   Separate function, to find the target worth value
*
* @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;
}
}
};
/**
*   According to order No.     Find several
*
* @param order
*              Order number, from the   1   Start
* @return
*/
OrderStatistic.prototype.getByOrder = function(order) {
if (this.inputArr.length == 0 || this.inputArr.length < order) {
} else {
var i = order - 1; // index   From 0  ,  The sequence number starting from 1  ,  Be adjusted here
return this.partition(i);
}
};

/**
*   Delimited single     The return value after the
*
* @param ok
*            boolean   Values that     It has been found
* @param subArr
*              Sub-array where the target value, when   ok = false   When using this array
* @param i
*              Target sub-array in order, from the   0   The beginning, when   ok = false   When using this value
* @param v
*              Target, when   ok = true   Only when using this value
* @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>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8" />
<script type="text/javascript" src="js/order_statistic.js"></script>
<body>
<input type="button" value="order statistic""var i = 6;alert(arr_order_statistic + '   In ,\n  Ranked '+ i +' position is  : '+ new OrderStatistic(arr_order_statistic).getByOrder(i));" />
</body>
</html>
```

*

------

• Medians and Order Statistics (order statistics) 2011-01-03

Medians and Order Statistics ------ Overview Order Statistics: Order statistics, that is ranked the number to find out n bits in the number of i, denoted by ith Medians: The median in the middle is the number of ------ Medians values Assuming all the

• Traffic statistics and statistics on the number line 2010-05-19

Lab requirements to do statistics and traffic statistics the number of online statistics, online enlist for a long time, this is not bad, keep for future use! 1, traffic statistics In the Solution Explorer add a new item, Global.asax, in which the co

• Binary tree of recursive initialization, and the first order, in order, after traversing 2010-06-29

#include<iostream> using namespace std; typedef struct BiTreeNode{ char data; BiTreeNode *lChild; BiTreeNode *rChild; }BiTreeNode; // Recursive build binary tree void InitialBiTree(BiTreeNode *&node) { char data; cout<<" Please enter

• Create STATISTICS,UPDATE STATISTICS 2015-03-24

该命令在一张表或者索引了的视图上更新查询优化统计数字信息. 默认情况下, 查询优化器已经更新了必要的用来提高查询计划的统计信息; 在某些情况下, 你可以通过使用UPDATE STATISTICS 命令或者存储过程sp_updatestats 来比默认更频繁地更新统计信息来提高查询效率. 更新统计信息能确保查询能以最新的统计信息来编译. 然而, 更新统计信息会引起查询的重新编译. 我们建议不要过于频繁地更新统计信息, 因为这里有一个在提高查询计划和用来重新编译查询的权衡. 具体的权衡要看你的应用程

• flex datagrid in numerical order, alphabetical order 2010-10-29

<? Xml version = "1.0" encoding = "utf-8"?> <! - http://blog.flexexamples.com/2008/03/07/performing-case-insensitive-sorts-using-the-datagrid-control-in-flex/ -> <MX: Application xmlns: MX = " http://www.adobe.com/2

• oracle multi-table queries Statistics Section of the function of the joint order by having sub-query set operations 2010-05-26

Joint multi-table query by connecting to a multi-table queries, multi-table query data can come from multiple tables, but the table must have an appropriate connection between the conditions. In order to query from multiple tables, you must identify

• [Order] informix statistics problem 2010-09-24

Description: Table derived from the production environment to the development test environment update, import table data to empty the original test environment, here is a single table import. When the informix data update, if they failed to update th

• joint multi-table query oracle, statistics query, group functions, order by, having, subqueries, set operations, 2011-08-22

Joint multi-table query by connecting to a multi-table queries, multi-table query data from multiple tables, but the table must have the appropriate connection between the conditions. In order to query from multiple tables, multiple tables must be id

• oracle statistics / analysis functions 2010-06-16

Oracle began offering analysis functions from 8.1.6 to analyze the function used to calculate the aggregate value based on a certain group, it's the difference between aggregate function is to return multiple rows for each group, and aggregate functi

• In Struts2 to use [interceptor] with [session listener] to achieve online membership statistics and to avoid duplication Login 2010-07-06

(Kazakhstan, which has indeed a very long title ...) Requirements: 1. Admin background to show the current number of online visitors and online membership (online list of members required to list in detail). 2. A client of illegal exit (close the bro

• Google Guava library usage order 2010-08-13

Reference: http://codemunchies.com/2009/10/beautiful-code-with-google-collections-guava-and-static-imports-part-1/ (2,3,4) http://blog.publicobject.com Before such a use: Map<String, Map<Long, List<String>>> map = new HashMap<String,

• Joint multi-table query oracle, statistical inquiry, group function, order by, having, subqueries, set operations 2011-01-07

Joint multi-table query oracle, statistical inquiry, group function, order by, having, subqueries, set operations, Keywords: oracle multi-table queries Statistics Section of the function of the joint order by having sub-query multiple tables combined

• Oracle: dbms_stats statistics on the difference between 9i and 10g 2011-06-16

About 2 months ago, an industry asked me why I moved to 10g on the 9i CBO will be many execution plans change in performance, he certainly was able to quiz me; in fact I talked to the environment mostly in 8i/9i CBO did not use optimization models un

• [Turn] to improve the efficiency of the SQL query where clause conditions the order of how to write SQL statements to fully optimize your 2011-07-03

To improve the efficiency of the SQL query where clause conditions the order of how to write your SQL statement to fully optimize the Category: Database 2010-11-10 18:17 33 Read Comments (0) Add report reproduced from suyineng Final edit suyineng Not

• Use HttpSessionListener statistics online 2008-12-02

Keywords: Using HttpSessionListener Statistics online statistics online using HttpSessionListener JSP displays the number of code line / ** * Write the following SessionCounter.java * And compiled to SessiionCounter.class * Then put your website in t

• web.xml, listener, filter, Servlet load order 2010-03-29

In the project will always encounter some problems on the priority of loading, also recently encountered a similar, and they therefore find the information summarized, the following are reproduced some other people, after all, the good people to writ

• Magento - Edit and Rorder order difference operator 2010-03-30

Edit order and Rorder user interface is very similar, but distinct * Edit The original order status was revised to cancle, then re-create an order to produce a new order number. * Reorder The original order remain unchanged, as if the same copy of th

• ORACLE CBO brief automatic statistics Statistics 2010-03-21

Introducing Oracle 10g automatic statistics CBO statistics function, but the actual use of them is tasteless, bug a lot. Is a brief introduction. 1, see GATHER_STATS_JOB implementation select JOB_NAME, LAST_START_DATE, ENABLED, state from dba_schedul

• [Order] sql statement some practical tips for oracle 2010-03-30

Finishing a book read long ago, and forgot what this was, now contributed. 1) In the select statement, use conditional logic 1select ename, sal, 2 case when sal <= 2000 then 'UNDERPAID' 3 when sal> = 4000 then 'OVERPAID' 4 else 'OK' 5 end as status

• long long type of network byte order conversion 2010-04-29

long long type of network byte order conversion sailor_forever [email protected] reproduced please specify http://blog.csdn.net/sailor_8318/archive/2007/08/04/1726064.aspx Socket did we know what network byte conversion, data transmission network

1
2
3
4
5