Selection algorithm (original) (raw)
خوارزمية الاختيار (بالإنجليزية: selection algorithm) هي لايجاد مكان عدد بالترتيب حسب التصنيف وتعد هذه الخوارزمية واحدة من أشهر الخوارزميات لانه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion
| Property | Value |
|---|---|
| dbo:abstract | خوارزمية الاختيار (بالإنجليزية: selection algorithm) هي لايجاد مكان عدد بالترتيب حسب التصنيف وتعد هذه الخوارزمية واحدة من أشهر الخوارزميات لانه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion (ar) En ciències de la computació, un algorisme de selecció és un algorisme dissenyat per trobar el k-èsim nombre més petit en una llista o vector. Aquest nombre s'anomena k. La selecció és un subproblema de problemes més complexos com els del veí més proper o camí més curt. Molts algorismes de selecció deriven de la generalització d'algorismes d'ordenació, i recíprocament alguns algorismes d'ordenació poden derivar-se en repetides aplicacions de selecció. L'algorisme de selecció més senzill és el problema de trobar el mínim o màxim element d'una llista per iteració, fent un seguiment del valor mínim (o màxim) actual durant aquesta. D'altra banda, trobar la mediana és l'algorisme de selecció més complex, el qual necessita una memòria n/2 (essent n el nombre d'elements de la llista o vector). L'algorisme de selecció conegut amb millor eficiència és el , que està relacionat amb l'algorisme d'ordenament Quicksort. (ca) En ciencias de la computación, un algoritmo de selección es un algoritmo para encontrar el k-ésimo menor número en una lista o vector; a este número se le llama estadístico de orden k. Este incluye los casos de encontrar el mínimo, máximo, y la mediana. Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados. La selección es un subproblema de otros problemas más complejos, como el y problema del camino más corto. Muchos algoritmos de selección son derivados por generalización de algún algoritmo de ordenación, y recíprocamente algunos algoritmos de ordenación pueden derivarse de repetidas aplicaciones de selección. El caso más simple de un algoritmo de selección es encontrar el mínimo (o máximo) elemento por iteración a través de la lista, manteniendo un registro del mínimo (o máximo) en cada paso de la iteración, y puede verse relacionado al selection sort. Por el contrario, el caso más complejo de un algoritmo de selección es encontrar la mediana, y este necesariamente necesita n/2 memoria. De hecho, un algoritmo de selección especializado para la mediana puede ser usado para realizar un algoritmo de selección general, como en . El algoritmo de selección más conocido es , el cual está relacionado al quicksort; como el quicksort, tiene (asintóticamente) rendimiento óptimo en la media de los casos, pero mal rendimiento en el peor caso, no obstante puede ser modificado para dar rendimiento óptimo en el peor caso también. (es) Dalam ilmu komputer, sebuah algoritme pemilihan adalah sebuah algoritme untuk menemukan bilangan terkecil ke-k (bilangan terbesar ke-k) dalam sebuah list. Termasuk di dalamnya adalah kasus sederhana yang lazim yaitu menemukan elemen minimum, maksimum dan median. Algoritme ini disebu juga orde statistik. Terdapat algoritme yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-k dengan waktu linear. Algoritme ini juga memungkinkan untuk menemukan elemen terkecil ke-k dalam waktu linear yang paling buruk atau orde statistik berlipat. Seleksi adalah sebuah sub masalah dari permasalahan yang lebih kompleks seperti . (in) In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection. The simplest case of a selection algorithm is finding the minimum (or maximum) element by iterating through the list, keeping track of the running minimum – the minimum so far – (or maximum) and can be seen as related to the selection sort. Conversely, the hardest case of a selection algorithm is finding the median. In fact, a specialized median-selection algorithm can be used to build a general selection algorithm, as in median of medians. The best-known selection algorithm is Quickselect, which is related to Quicksort; like Quicksort, it has (asymptotically) optimal average performance, but poor worst-case performance, though it can be modified to give optimal worst-case performance as well. (en) En algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc. Le problème de la sélection est très lié aux algorithmes de tri : l'un des algorithmes classiques, Quickselect, utilise d'ailleurs le même principe que l'algorithme de tri Quicksort. (fr) 選択アルゴリズム（英: selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。 (ja) В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n). (ru) 在计算机科学中，选择算法是一种在列表或数组中找到第k个最小数字的算法；这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种：最小、最大和中位数。已知存在O(n)（最坏情况下为线性时间）的选择算法，还有对于结构化数据可能有次线性的表现的算法；在极端的情况下，对于已排序数据是O(1)。选择是一些更复杂问题的子问题，如最近邻和最短路径问题。 许多选择算法是由排序算法推广而来，反之，一些排序算法可由反复应用选择算法推导出来。 最简单的选择算法是通过遍历列表找到最小（或最大）的元素，在此过程中跟踪当前的最小（或最大）值。这种算法与选择排序有关。相反地，最困难的选择算法是寻找中位数，这必然需要n/2的空间。 事实上，一个专门的中位选择算法可用来构造一个一般选择算法，例如。已知最好的选择算法是快速选择（quickselect），它与快速排序有关。和快速排序类似，它有渐进最佳的复杂度，但是最坏情况的复杂度较差。不过这可以通过调整基准（pivot）的选择来优化。 (zh) Пошук порядкової статистики i-ю порядковою статистикою (англ. order statistic) множини з n елементів називається i-й у порядку зростання елемент множини. Так мінімум множини — це перша порядкова статистика, а максимум — n-та порядкова статистика. Медіа́на (англ. median) неформально означає середину множини. Якщо n непарне, то медіана єдина, і її індекс (індекс відповідної порядкової статистики) дорівнює i = (n + 1) / 2; якщо ж n парне, то медіани дві: i = n / 2 та i = n / 2 + 1. Формально задача пошуку порядкової статистики визначається так: Дано: множину, що складається з (різних) чисел, і число Потрібно знайти: елемент , що більший за рівно інших елементів множини. Задачу можна розв'язати за час. Для цього достатньо впорядкувати елементи за зростанням, а потім взяти i-й елемент. Але є алгоритми що можуть розв'язати цю задачу за час в середньому і навіть у найгіршому випадках. (uk) |
| dbo:wikiPageExternalLink | http://people.csail.mit.edu/rivest/pubs/BFPRT73.pdf%7C https://metacpan.org/module/Sort::Key::Top https://metacpan.org/module/Statistics::CaseResampling http://www.ics.uci.edu/~eppstein/161/960125.html |
| dbo:wikiPageID | 552786 (xsd:integer) |
| dbo:wikiPageLength | 22273 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1110849589 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Python_(programming_language) dbr:Quicksort dbr:Algorithm dbr:Perl dbr:Descriptive_statistics dbr:Introduction_to_Algorithms dbr:Introselect dbr:Introsort dbr:Thomas_H._Cormen dbr:Matlab dbr:Maximum dbr:Median dbr:Online_algorithm dbr:Order_statistic_tree dbr:Clifford_Stein dbr:Geometric_series dbr:Shortest_path dbr:Computer_science dbr:Median_of_medians dbr:C++ dbr:Heap_(data_structure) dbr:Lazy_evaluation dbr:List_(abstract_data_type) dbr:Quickselect dbr:Amortized_analysis dbr:Partial_sorting dbr:Reduction_(complexity) dbr:Hash_table dbr:Counting_sort dbr:Array_data_structure dbr:Charles_E._Leiserson dbr:Odds_algorithm dbr:Divide_and_conquer_algorithm dbr:Donald_E._Knuth dbr:Donald_Knuth dbc:Selection_algorithms dbr:CPAN dbr:Sorting_algorithm dbr:Minimum dbr:Order_statistic dbr:Ordinal_optimization dbr:Radix_sort dbr:Search_algorithm dbr:Selection_sort dbr:The_Art_of_Computer_Programming dbr:Range_Queries dbr:Secretary_problem dbr:Self-balancing_binary_search_tree dbr:Random_access dbr:Frequency_tables dbr:Almost_certain dbr:Nearest_neighbor_problem dbr:Ronald_L._Rivest dbr:Sublinear_time |
| dbp:wikiPageUsesTemplate | dbt:Anchor dbt:Citation_needed dbt:Cite_journal dbt:DADS dbt:Expand_section dbt:For dbt:Further dbt:ISBN dbt:More_footnotes dbt:Refbegin dbt:Refend dbt:Reflist dbt:Short_description |
| dcterms:subject | dbc:Selection_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatSelectionAlgorithms yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 yago:WikicatAlgorithms |
| rdfs:comment | خوارزمية الاختيار (بالإنجليزية: selection algorithm) هي لايجاد مكان عدد بالترتيب حسب التصنيف وتعد هذه الخوارزمية واحدة من أشهر الخوارزميات لانه يمكن تطبيقها بزمن خطي ولاستخداماتها المتعددة في علوم الحاسوب والطريقة التي تتم بها عن طريق الاستدعاء الذاتي أو recursion (ar) Dalam ilmu komputer, sebuah algoritme pemilihan adalah sebuah algoritme untuk menemukan bilangan terkecil ke-k (bilangan terbesar ke-k) dalam sebuah list. Termasuk di dalamnya adalah kasus sederhana yang lazim yaitu menemukan elemen minimum, maksimum dan median. Algoritme ini disebu juga orde statistik. Terdapat algoritme yang relatif sederhana untuk menemukan, minimum, maksimum, dan element terkecil ke-k dengan waktu linear. Algoritme ini juga memungkinkan untuk menemukan elemen terkecil ke-k dalam waktu linear yang paling buruk atau orde statistik berlipat. Seleksi adalah sebuah sub masalah dari permasalahan yang lebih kompleks seperti . (in) 選択アルゴリズム（英: selection algorithm）とは、数列から k 番目に小さい（あるいは k 番目に大きい）数を探すアルゴリズムである。最小値、最大値、中央値を探すアルゴリズムは選択アルゴリズムの特殊なものと言える。これらを「順序統計量」とも呼ぶ。比較的単純な最小値、最大値、k 番目に小さい値を求めるアルゴリズムとしては、平均で線形時間のものが知られている。k 番目に小さい値や一度に複数の順序統計量を最悪でも線形時間で探すことも可能である。選択は最近傍探索問題や最短経路問題のようなもっと複雑な問題の部分問題である。 (ja) В информатике алгоритм выбора — это алгоритм для нахождения k-го по величине элемента в массиве (такой элемент называется k-й порядковой статистикой). Частными случаями этого алгоритма являются нахождение минимального элемента, максимального элемента и медианы. Существует алгоритм, который гарантированно решает задачу выбора k-го по величине элемента за O(n). (ru) 在计算机科学中，选择算法是一种在列表或数组中找到第k个最小数字的算法；这样的数字被称为第k个顺序统计量。该算法寻找的对象主要有三种：最小、最大和中位数。已知存在O(n)（最坏情况下为线性时间）的选择算法，还有对于结构化数据可能有次线性的表现的算法；在极端的情况下，对于已排序数据是O(1)。选择是一些更复杂问题的子问题，如最近邻和最短路径问题。 许多选择算法是由排序算法推广而来，反之，一些排序算法可由反复应用选择算法推导出来。 最简单的选择算法是通过遍历列表找到最小（或最大）的元素，在此过程中跟踪当前的最小（或最大）值。这种算法与选择排序有关。相反地，最困难的选择算法是寻找中位数，这必然需要n/2的空间。 事实上，一个专门的中位选择算法可用来构造一个一般选择算法，例如。已知最好的选择算法是快速选择（quickselect），它与快速排序有关。和快速排序类似，它有渐进最佳的复杂度，但是最坏情况的复杂度较差。不过这可以通过调整基准（pivot）的选择来优化。 (zh) En ciències de la computació, un algorisme de selecció és un algorisme dissenyat per trobar el k-èsim nombre més petit en una llista o vector. Aquest nombre s'anomena k. La selecció és un subproblema de problemes més complexos com els del veí més proper o camí més curt. Molts algorismes de selecció deriven de la generalització d'algorismes d'ordenació, i recíprocament alguns algorismes d'ordenació poden derivar-se en repetides aplicacions de selecció. L'algorisme de selecció conegut amb millor eficiència és el , que està relacionat amb l'algorisme d'ordenament Quicksort. (ca) En ciencias de la computación, un algoritmo de selección es un algoritmo para encontrar el k-ésimo menor número en una lista o vector; a este número se le llama estadístico de orden k. Este incluye los casos de encontrar el mínimo, máximo, y la mediana. Existen algoritmos de selección O(n) (lineal en el peor caso), y algoritmos sublineales son posibles para datos estructurados; en el caso extremos, O(1) para un vector de elementos ordenados. La selección es un subproblema de otros problemas más complejos, como el y problema del camino más corto. Muchos algoritmos de selección son derivados por generalización de algún algoritmo de ordenación, y recíprocamente algunos algoritmos de ordenación pueden derivarse de repetidas aplicaciones de selección. (es) En algorithmique, un algorithme de sélection est une méthode ayant pour but de trouver le k-ième plus petit élément d'un ensemble d'objets (étant donné un ordre et un entier k). La question de la sélection est un problème essentiel en algorithmique, notamment dans la recherche du maximum, du minimum et de la médiane. Plusieurs algorithmes ont été proposés et plusieurs contextes ont été étudiés : algorithmes en ligne, complexité amortie, complexité en moyenne, ensemble d'objet particuliers etc. (fr) In computer science, a selection algorithm is an algorithm for finding the kth smallest number in a list or array; such a number is called the kth order statistic. This includes the cases of finding the minimum, maximum, and median elements. There are O(n)-time (worst-case linear time) selection algorithms, and sublinear performance is possible for structured data; in the extreme, O(1) for an array of sorted data. Selection is a subproblem of more complex problems like the nearest neighbor and shortest path problems. Many selection algorithms are derived by generalizing a sorting algorithm, and conversely some sorting algorithms can be derived as repeated application of selection. (en) Пошук порядкової статистики i-ю порядковою статистикою (англ. order statistic) множини з n елементів називається i-й у порядку зростання елемент множини. Так мінімум множини — це перша порядкова статистика, а максимум — n-та порядкова статистика. Медіа́на (англ. median) неформально означає середину множини. Якщо n непарне, то медіана єдина, і її індекс (індекс відповідної порядкової статистики) дорівнює i = (n + 1) / 2; якщо ж n парне, то медіани дві: i = n / 2 та i = n / 2 + 1. Формально задача пошуку порядкової статистики визначається так: Дано: множину, що складається з (різних) чисел, і число (uk) |
| rdfs:label | خوارزمية الاختيار (ar) Algorisme de selecció (ca) Algoritmo de selección (es) Algorithme de sélection (fr) Algoritma seleksi (in) Selection algorithm (en) 選択アルゴリズム (ja) 선택 알고리즘 (ko) Алгоритм выбора (ru) Пошук порядкової статистики (uk) 选择算法 (zh) |
| owl:sameAs | freebase:Selection algorithm yago-res:Selection algorithm wikidata:Selection algorithm dbpedia-ar:Selection algorithm dbpedia-ca:Selection algorithm dbpedia-es:Selection algorithm dbpedia-fa:Selection algorithm dbpedia-fr:Selection algorithm dbpedia-hu:Selection algorithm dbpedia-id:Selection algorithm dbpedia-ja:Selection algorithm dbpedia-ko:Selection algorithm dbpedia-ru:Selection algorithm dbpedia-sr:Selection algorithm dbpedia-tr:Selection algorithm dbpedia-uk:Selection algorithm dbpedia-zh:Selection algorithm https://global.dbpedia.org/id/31649 |
| prov:wasDerivedFrom | wikipedia-en:Selection_algorithm?oldid=1110849589&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Selection_algorithm |
| is dbo:wikiPageDisambiguates of | dbr:Selection |
| is dbo:wikiPageRedirects of | dbr:Maximum_algorithm dbr:Hoare's_algorithm dbr:Introspective_selection dbr:Minimum_algorithm dbr:Select_algorithm dbr:Select_and_partition dbr:Select_kth_element dbr:Selection_problem dbr:Median_algorithm dbr:Median_search |
| is dbo:wikiPageWikiLink of | dbr:Quicksort dbr:Robert_Tarjan dbr:List_of_algorithms dbr:Algorithm dbr:C++_Standard_Library dbr:Vaughan_Pratt dbr:David_Musser dbr:Introselect dbr:Introsort dbr:Mathematics dbr:Median dbr:Order_statistic_tree dbr:Rectilinear_Steiner_tree dbr:Simplex dbr:Medcouple dbr:Median_of_medians dbr:Heap_(data_structure) dbr:K-d_tree dbr:Quickselect dbr:Floyd–Rivest_algorithm dbr:Football_League_Jujeña_1928 dbr:Partial_sorting dbr:BRS-inequality dbr:Theil–Sen_estimator dbr:Manuel_Blum dbr:Sorting_algorithm dbr:Maximum_algorithm dbr:In-place_algorithm dbr:Order_statistic dbr:Selection_sort dbr:Median_filter dbr:Selection dbr:Skyline_operator dbr:Sort_(C++) dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Science_and_technology_in_Venezuela dbr:Secretary_problem dbr:Soft_heap dbr:Uniform_matroid dbr:Hoare's_algorithm dbr:Introspective_selection dbr:Minimum_algorithm dbr:Select_algorithm dbr:Select_and_partition dbr:Select_kth_element dbr:Selection_problem dbr:Median_algorithm dbr:Median_search |
| is dbp:class of | dbr:Median_of_medians dbr:Quickselect dbr:Floyd–Rivest_algorithm |
| is foaf:primaryTopic of | wikipedia-en:Selection_algorithm |