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