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) {
                alert('  Entered incorrectly  !');
        } 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>
<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""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