Median of medians (original) (raw)
La médiane des médianes est un algorithme de sélection pour trouver le kième élément le plus grand au sein d'une liste non triée. Il est basé sur l'algorithme Quickselect. Cet algorithme est optimal dans le pire cas, avec une complexité en temps linéaire. La brique de base de l'algorithme est la sélection d'une médiane approchée en temps linéaire.L'algorithme est parfois appelé BFPRT d'après les noms des auteurs : Blum, Floyd, (en), Rivest et Tarjan.
| Property | Value |
|---|---|
| dbo:abstract | La médiane des médianes est un algorithme de sélection pour trouver le kième élément le plus grand au sein d'une liste non triée. Il est basé sur l'algorithme Quickselect. Cet algorithme est optimal dans le pire cas, avec une complexité en temps linéaire. La brique de base de l'algorithme est la sélection d'une médiane approchée en temps linéaire.L'algorithme est parfois appelé BFPRT d'après les noms des auteurs : Blum, Floyd, (en), Rivest et Tarjan. (fr) In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the kth smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time only, which is limited but an additional overhead for quickselect. When this approximate median is used as an improved pivot, the worst-case complexity of quickselect reduces significantly from quadratic to linear, which is also the asymptotically optimal worst-case complexity of any selection algorithm. In other words, the median of medians is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm (especially in the sense of worst-case complexity), by producing good pivot elements. Median of medians can also be used as a pivot strategy in quicksort, yielding an optimal algorithm, with worst-case complexity . Although this approach optimizes the asymptotic worst-case complexity quite well, it is typically outperformed in practice by instead choosing random pivots for its average complexity for selection and average complexity for sorting, without any overhead of computing the pivot. Similarly, Median of medians is used in the hybrid introselect algorithm as a fallback for pivot selection at each iteration until kth smallest is found. This again ensures a worst-case linear performance, in addition to average-case linear performance: introselect starts with quickselect (with random pivot, default), to obtain good average performance, and then falls back to modified quickselect with pivot obtained from median of medians if the progress is too slow. Even though asymptotically similar, such a hybrid algorithm will have a lower complexity than a straightforward introselect up to a constant factor (both in average-case and worst-case), at any finite length. The algorithm was published in , and thus is sometimes called BFPRT after the last names of the authors. In the original paper the algorithm was referred to as PICK, referring to quickselect as "FIND". (en) In informatica, BFPRT (Blum, Floyd, , Rivest, Tarján) è un algoritmo in quattro passi, utile alla selezione dell'ennesimo elemento più piccolo di un array disordinato. (it) Algorytm magicznych piątek (znany też jako „mediana median”) – algorytm rozwiązujący problem , czyli znalezienia -tej co do wielkości spośród liczb. Zaproponowali go Blum, Floyd, Pratt, Rivest i Tarjan w roku 1973. Jest on oparty na prostszym algorytmie rozwiązującym ten sam problem, algorytmie Hoare’a. (pl) 中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 (ja) |
| dbo:wikiPageExternalLink | http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf%7C http://www.ics.uci.edu/~eppstein/161/960130.html |
| dbo:wikiPageID | 40327133 (xsd:integer) |
| dbo:wikiPageLength | 18339 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110849522 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Quicksort dbr:Decile dbr:Decision_tree dbr:Dutch_national_flag_problem dbr:Insertion_sort dbr:Introselect dbr:Median dbr:Geometric_series dbr:Computer_science dbr:Mutual_recursion dbr:Triangular_number dbr:Percentile dbr:Quickselect dbr:Akra–Bazzi_method dbr:Array_data_structure dbr:Divide_and_conquer_algorithm dbc:Selection_algorithms dbr:Recursion_(computer_science) dbr:Selection_algorithm dbr:Pseudocode |
| dbp:class | dbr:Selection_algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:name | Median of Medians (en) |
| dbp:optimal | Yes (en) |
| dbp:space | auxiliary (en) |
| dbp:wikiPageUsesTemplate | dbt:Cite_journal dbt:Harvtxt dbt:Mono dbt:More_footnotes dbt:Mvar dbt:R dbt:Refbegin dbt:Refend dbt:Reflist dbt:See_also dbt:Infobox_Algorithm |
| dcterms:subject | dbc:Selection_algorithms |
| rdf:type | owl:Thing yago:WikicatSelectionAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 |
| rdfs:comment | La médiane des médianes est un algorithme de sélection pour trouver le kième élément le plus grand au sein d'une liste non triée. Il est basé sur l'algorithme Quickselect. Cet algorithme est optimal dans le pire cas, avec une complexité en temps linéaire. La brique de base de l'algorithme est la sélection d'une médiane approchée en temps linéaire.L'algorithme est parfois appelé BFPRT d'après les noms des auteurs : Blum, Floyd, (en), Rivest et Tarjan. (fr) In informatica, BFPRT (Blum, Floyd, , Rivest, Tarján) è un algoritmo in quattro passi, utile alla selezione dell'ennesimo elemento più piccolo di un array disordinato. (it) Algorytm magicznych piątek (znany też jako „mediana median”) – algorytm rozwiązujący problem , czyli znalezienia -tej co do wielkości spośród liczb. Zaproponowali go Blum, Floyd, Pratt, Rivest i Tarjan w roku 1973. Jest on oparty na prostszym algorytmie rozwiązującym ten sam problem, algorytmie Hoare’a. (pl) 中央値の中央値（ちゅうおうちのちゅうおうち、英: median of medians）とは、クイックセレクトに基づく選択アルゴリズムのことである。k番目に大きい要素を選択するための最悪計算時間が線形になることが特徴である。 このアルゴリズムでは、最初におおよその中央値を線形時間で探索し、その値をクイックセレクトでのピボット値とする。つまり、（漸近的な）おおよその中央値選択アルゴリズムを使って、（漸近的な）一般値選択アルゴリズムを構築したものである。 このアルゴリズムは、マヌエル・ブラムらによって開発されたもので、著者の名字の頭文字を取ってBFPRTとも呼ばれる。この原著では中央値の中央値アルゴリズムをPICKと呼び、クイックセレクトをFINDと呼んでいた。 (ja) In computer science, the median of medians is an approximate (median) selection algorithm, frequently used to supply a good pivot for an exact selection algorithm, mainly the quickselect, that selects the kth smallest element of an initially unsorted array. Median of medians finds an approximate median in linear time only, which is limited but an additional overhead for quickselect. When this approximate median is used as an improved pivot, the worst-case complexity of quickselect reduces significantly from quadratic to linear, which is also the asymptotically optimal worst-case complexity of any selection algorithm. In other words, the median of medians is an approximate median-selection algorithm that helps building an asymptotically optimal, exact general selection algorithm (especially (en) |
| rdfs:label | Médiane des médianes (fr) BFPRT (it) Median of medians (en) 中央値の中央値 (ja) Algorytm magicznych piątek (pl) |
| rdfs:seeAlso | dbr:Dutch_national_flag_problem |
| owl:sameAs | dbpedia-it:Median of medians freebase:Median of medians yago-res:Median of medians wikidata:Median of medians dbpedia-fa:Median of medians dbpedia-fr:Median of medians dbpedia-ja:Median of medians dbpedia-pl:Median of medians https://global.dbpedia.org/id/3MijA |
| prov:wasDerivedFrom | wikipedia-en:Median_of_medians?oldid=1110849522&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Median_of_medians |
| is dbo:wikiPageRedirects of | dbr:BFPRT dbr:Median_of_5 dbr:Median_of_Medians_algorithm |
| is dbo:wikiPageWikiLink of | dbr:Cache-oblivious_distribution_sort dbr:Quicksort dbr:Robert_Tarjan dbr:Vaughan_Pratt dbr:Introselect dbr:Introsort dbr:Median dbr:Range_query_(data_structures) dbr:K-d_tree dbr:Quickselect dbr:Floyd–Rivest_algorithm dbr:Partial_sorting dbr:Hybrid_algorithm dbr:BFPRT dbr:Manuel_Blum dbr:Sorting_algorithm dbr:Selection_algorithm dbr:External_sorting dbr:Science_and_technology_in_Venezuela dbr:Median_of_5 dbr:Median_of_Medians_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Median_of_medians |