Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Мазмұны
Кіріспе
k-шы ең кіші мәнді табу әдісі: генетикалық алгоритмдерде табиғи іріктеуді модельдеу
Method for finding kth smallest value
simulated natural selection in genetic algorithms
Компьютерлік ғылымда іріктеу алгоритмі – сандар сияқты реттелген мәндер жиынтығында k-шы ең кіші мәнді табуға арналған алгоритм. Ол тапқан мән k-шы реттік статистика деп аталады. Іріктеу, жинақтағы ең кіші, медиана және ең жоғары элементті табу мәселелерін арнайы жағдайлар ретінде қамтиды. Іріктеу алгоритмдеріне жылдам іріктеу және медиандар медианасы алгоритмі жатады. Мәндер жиынтығына қолданғанда, бұл алгоритмдер үлкен O нотациясымен көрсетілгендей, сызықтық уақыт алады. Бұрыннан құрылымдалған деректер үшін жылдам алгоритмдер мүмкін; ең шекті жағдай ретінде, бұрыннан сұрыпталған массивтегі іріктеу уақыт алады.
In computer science, a selection algorithm is an algorithm for finding the th smallest value in a collection of ordered values, such as numbers. The value that it finds is called the th order statistic. Selection includes as special cases the problems of finding the minimum, median, and maximum element in the collection. Selection algorithms include quickselect, and the median of medians algorithm. When applied to a collection of values, these algorithms take linear time, as expressed using big O notation. For data that is already structured, faster algorithms may be possible; as an extreme case, selection in an already sorted array takes time .
Мәселе туралы мәлімдеме
Таңдау мәселесі үшін алгоритм мәндер жиынтығын және бір санды кіріс ретінде қабылдайды. Ол осы мәндердің k-шы ең кішісін шығарады немесе, мәселенің кейбір нұсқаларында, k ең кіші мәндердің жиынтығын шығарады. Бұл жақсы анықталған болуы үшін, мәндерді кішісінен үлкеніне қарай реттеу мүмкін болуы керек; мысалы, олар бүтін сандар, қалқыма нүктелі сандар немесе сандық кілті бар кез келген нысан болуы мүмкін. Дегенмен, олардың бұрыннан реттелгендігі туралы ешқандай болжам жасалмайды. Көбінесе таңдау алгоритмдері салыстыруға негізделген есептеу моделімен шектеледі, мысалы, салыстыру арқылы сұрыптау алгоритмдеріндегідей, онда алгоритм кез келген екі мәннің салыстырмалы ретін анықтай алатын салыстыру операциясына қол жеткізе алады, бірақ осы мәндер бойынша басқа арифметикалық операцияларды орындай алмайды. Мәселені жеңілдету үшін, осы мәселе бойынша кейбір зерттеулер мәндердің барлығының бір-бірінен ерекшеленетінін немесе бірдей мәнді элементтер жұптарына рет беру үшін дәйекті түрде түйін шешу әдісі қолданылғанын болжайды. Мәселе анықтамасындағы тағы бір өзгеріс реттелген мәндерді нөмірлеуге қатысты: ең кіші мән массивттерді нөлден бастап нөмірлеудегідей, яғни k=0 арқылы алына ма, әлде «ең кіші, екінші ең кіші» сияқты ағылшын тіліндегі дәстүрлі конвенцияларды ұстана отырып, k=1 арқылы алына ма? Осы мақала Cormen және авторлар қолданған конвенцияларды ұстанады, оларға сәйкес барлық мәндер ерекше және ең кіші мән k=1 арқылы алынады.
An algorithm for the selection problem takes as input a collection of values, and a number It outputs the th smallest of these values, or, in some versions of the problem, a collection of the smallest values. For this to be well defined, it should be possible to sort the values into an order from smallest to largest; for instance, they may be integers, floating point numbers, or some other kind of object with a numeric key. However, they are not assumed to have been already sorted. Often, selection algorithms are restricted to a comparison based model of computation, as in comparison sort algorithms, where the algorithm has access to a comparison operation that can determine the relative ordering of any two values, but may not perform any other kind of arithmetic operations on these values. To simplify the problem, some works on this problem assume that the values are all distinct from each or that some consistent tie breaking method has been used to assign an ordering to pairs of items with the same value as each other. Another variation in the problem definition concerns the numbering of the ordered values: is the smallest value obtained by setting , as in zero based numbering of arrays, or is it obtained by setting , following the usual English language conventions for the smallest, second smallest, etc.? This article follows the conventions used by Cormen et al., according to which all values are distinct and the minimum value is obtained from
Осы конвенциялар бойынша, мәндер жиынтығының ішіндегі ең жоғары мән, k=n арқылы алынады. Егер n тақ сан болса, жиынтықтың медианасы k= (n+1)/2 арқылы алынады. Егер n жұп сан болса, медиананы алу үшін екі мүмкіндік бар: осы k мәнін төменге немесе жоғарыға дөңгелектеу арқылы, яғни төменгі медиана k=n/2 және жоғарғы медиана k=n/2 + 1 арқылы.
With these conventions, the maximum value, among a collection of values, is obtained by setting When is an odd number, the median of the collection is obtained by setting When is even, there are two choices for the median, obtained by rounding this choice of down or up, respectively: the lower median with and the upper median with
Зауыттар
Детерминистік таңдау алгоритмдері, -қа немесе -қа қашық жатқан мәндер үшін, салыстырулардың ең кіші белгілі санымен, 1976 жылы Арнольд Шёнхаге, Майк Паттерсон және олар енгізген фабрикалар тұжырымдамасына негізделген. Бұл әдістер кіріс мәндерінің кіші топтарында белгілі бір типтегі ішінара реттіліктерді құрады, салыстыру арқылы кішірек ішінара реттіліктерді біріктіру арқылы. Мысалы, зауыттың бір түрі бір элементтен тұратын ішінара реттіліктер тізбегін кіріс ретінде қабылдап, осы реттіліктерден элементтер жұптарын салыстырып, шығыс ретінде екі элементтен тұратын толық реттелген жиынтар тізбегін шығарады. Бұл зауытқа кіріс ретінде берілетін элементтер әлі салыстырылмаған кіріс мәндері немесе басқа зауыттар жасаған "қалдық" мәндер болуы мүмкін. Фабрикаға негізделген алгоритмнің мақсаты – әртүрлі зауыттарды біріктіру, кейбір зауыттардың шығыстарын басқаларының кірістері ретінде пайдаланып, ақырында бір элементтің ( ең кіші элементтің) басқа элементтерден үлкен және тағы бір элементтен кіші болатын ішінара реттілік алу. Бұл фабрикалардың мұқият жобалануы медиананы табу үшін қолданылғанда ең көп салыстыруды қажет ететін алгоритмге әкеледі. Басқа мәндері үшін салыстырулар саны –қа тең болады.
The deterministic selection algorithms with the smallest known numbers of comparisons, for values of that are far from or , are based on the concept of factories, introduced in 1976 by Arnold Schönhage, Mike Paterson, and These are methods that build partial orders of certain specified types, on small subsets of input values, by using comparisons to combine smaller partial orders. As a very simple example, one type of factory can take as input a sequence of single element partial orders, compare pairs of elements from these orders, and produce as output a sequence of two element totally ordered sets. The elements used as the inputs to this factory could either be input values that have not been compared with anything yet, or "waste" values produced by other factories. The goal of a factory based algorithm is to combine together different factories, with the outputs of some factories going to the inputs of others, in order to eventually obtain a partial order in which one element (the th smallest) is larger than some other elements and smaller than another others. A careful design of these factories leads to an algorithm that, when applied to median finding, uses at most comparisons. For other values of , the number of comparisons is
Сублинериялық дерек құрылымдары
Деректер деректер құрылымына ұйымдастырылған кезде, мәндер санына қатысты сызықтық емес уақытта таңдау жасау мүмкін. Бұның ең қарапайым мысалы ретінде, массивке реттелген деректер үшін k-шы элементті бір массивтік іздеу арқылы тұрақты уақытта таңдауға болады. Екі өлшемді массивке реттелген мәндер үшін, реттелген жолдар мен бағандармен, таңдау уақыты O(n) болады, ал n массивінің өлшеміне қатысты кіші болғанда, одан да жылдам орындалуы мүмкін. Бір өлшемді реттелген массивтер жиынтығында, k-шы массивтегі таңдалған элементтен кіші элементтердің саны болса, уақыт O(n) болады.
When data is already organized into a data structure, it may be possible to perform selection in an amount of time that is sublinear in the number of values. As a simple case of this, for data already sorted into an array, selecting the th element may be performed by a single array lookup, in constant For values organized into a two dimensional array of size , with sorted rows and columns, selection may be performed in time , or faster when is small relative to the array For a collection of one dimensional sorted arrays, with items less than the selected item in the th array, the time is
Бұл әдіс үйіндідегі таңдауды орындау үшін де қолданылады. Бұл үйіндінің өлшеміне тәуелсіз және O(n) уақытынан жылдам. Осы әдіс кез келген үйінділік ағаш ретімен ұйымдастырылған деректерге де қолданылуы мүмкін (әртүрлі түйіндердегі мәндерде әкесі баласынан кіші болатын ағаш). Бұл әдіс комбинаторлық оптимизация мәселелерін шешуге, мысалы, салмақты графиктердегі k ең қысқа жолды табуға қолданылды, шешімдер кеңістігін жасырын түрде анықталған үйінділік ағаш түрінде анықтап, содан кейін осы таңдау алгоритмін қолдану арқылы. Керісінше, сызықтық уақытты таңдау алгоритмдері үйіндіге байланысты басымдық кезек деректер құрылымында қолданылды, оның k-шы элементін алу уақытын O(n) -дан O(log n) -ға дейін жақсартады.
Selection from data in a binary heap takes time This is independent of the size of the heap, and faster than the time bound that would be obtained from This same method can be applied more generally to data organized as any kind of heap ordered tree (a tree in which each node stores one value in which the parent of each non root node has a smaller value than its child). This method of performing selection in a heap has been applied to problems of listing multiple solutions to combinatorial optimization problems, such as finding the k shortest paths in a weighted graph, by defining a state space of solutions in the form of an implicitly defined heap ordered tree, and then applying this selection algorithm to this In the other direction, linear time selection algorithms have been used as a subroutine in a priority queue data structure related to the heap, improving the time for extracting its th item from to ; here is the
Динамикалық енгізулер мен жоюлар болатын деректер жиынтығы үшін, реттік статистикалық ағаш өзін-өзі теңгерілген бинарлық іздеу ағашы құрылымын әрбір түйін үшін тұрақты мөлшерде қосымша ақпаратпен толықтырады, енгізулерге, жоюларға және ағымдағы жиынның k-шы элементін сұрауға мүмкіндік береді, бәрі O(log n) уақытта орындалады. Есептеудің салыстыру моделінен арылып, кіші бүтін сандар үшін операцияларға қатысты жылдам уақыттарға қол жеткізуге болады, онда бинарлық арифметикалық операциялар қолданылады. Егер жад сызықтық емес болса, ағымдық алгоритм динамикалық деректер үшін таңдау сұрақтарын дәл шеше алмайды, бірақ санау-мин эскизі таңдау сұрақтарын шамамен шешу үшін қолданылуы мүмкін, егер элементтерге қосылғандағы олардың реттіліктегі орны k-шы саннан бірнеше қадам қашықтықта болса, эскиздің өлшемі логарифмдік факторлармен шектелген.
For a collection of data values undergoing dynamic insertions and deletions, the order statistic tree augments a self balancing binary search tree structure with a constant amount of additional information per tree node, allowing insertions, deletions, and selection queries that ask for the th element in the current set to all be performed in time per Going beyond the comparison model of computation, faster times per operation are possible for values that are small integers, on which binary arithmetic operations are It is not possible for a streaming algorithm with memory sublinear in both and to solve selection queries exactly for dynamic data, but the count–min sketch can be used to solve selection queries approximately, by finding a value whose position in the ordering of the elements (if it were added to them) would be within steps of , for a sketch whose size is within logarithmic factors of .
Тілдік қолдау
Тілдердің өте азы ғана жалпы таңдауды қолдайды, бірақ көптегені тізімдегі ең кіші немесе ең үлкен элементті табу мүмкіндігін ұсынады. Назар аударарлық ерекшелік – C++ үшін жасалған Стандартты үлгі кітапханасы, ол күтілетін сызықтық уақыт кепілдігімен n-ші элемент әдісін ұсынады. Python стандартты кітапханасы (2.4 нұсқасынан бастап) heapq.nsmallest және heapq.nlargest кіші бағдарламаларын қамтиды, олар жиыннан ең кіші немесе ең үлкен элементтерді реттелген түрде қайтаруға арналған. Python-ның әртүрлі нұсқалары осы кіші бағдарламалар үшін әртүрлі алгоритмдерді пайдаланған. Python 3.13 нұсқасынан бастап, іске асыру бинарлық үйіндіні сақтайды, ол элементтерді сақтаумен шектеледі және жиынның алғашқы элементтерімен басталады. Содан кейін жиынның әрбір келесі элементі үйіндідегі ең үлкен немесе ең кіші элементті (сәйкесінше heapq.nsmallest және heapq.nlargest үшін) егер ол осы элементтен кіші немесе үлкен болса ауыстыра алады. Бұл іске асырудың ең нашар жағдайдағы уақыты , бұл heapselect арқылы қол жеткізілетін уақыттан нашар. Дегенмен, кездейсоқ енгізілген тізбектер үшін үйінді жаңартулар азырақ болуы мүмкін және көптеген кіріс элементтері тек бір салыстырумен өңделеді. 2017 жылдан бері Matlab maxk және mink функцияларын қосты, олар вектордағы ең үлкен (ең кіші) мәндерді, сондай-ақ олардың индекстерін қайтарады. Matlab құжаттамасында бұл функциялардың қандай алгоритмді қолданатыны немесе олардың жұмыс істеу принципі көрсетілмеген.
Very few languages have built in support for general selection, although many provide facilities for finding the smallest or largest element of a list. A notable exception is the Standard Template Library for C++, which provides a templated nth element method with a guarantee of expected linear time. Python's standard library (since 2.4) includes heapq. nsmallest and heapq. nlargest subroutines for returning the smallest or largest elements from a collection, in sorted order. Different versions of Python have used different algorithms for these subroutines. As of Python version 3.13, the implementation maintains a binary heap, limited to holding elements, and initialized to the first elements in the collection. Then, each subsequent items of the collection may replace the largest or smallest element in the heap (respectively for heapq. nsmallest and heapq. nlargest) if it is smaller or larger than this element. The worst case time for this implementation is , worse than the that would be achieved by heapselect. However, for random input sequences, there are likely to be few heap updates and most input elements are processed with only a single comparison. Since 2017, Matlab has included maxk and mink functions, which return the maximal (minimal) values in a vector as well as their indices. The Matlab documentation does not specify which algorithm these functions use or what their running
Тарих
Quickselect Тони Хоар тарапынан талдаусыз ұсынылды және алғаш рет 1971 жылғы техникалық есепте талданды. Бірінші белгілі сызықтық уақыт детерминистік таңдау алгоритмі – 1973 жылы Мануэль Блум, Роберт В. Флойд, Воган Пратт, Рон Ривест және Роберт Таржан жариялаған медианалардың медианасы әдісі. Олар таңдау мәселесінің қалыптасуын Чарльз Л. Доджсонның (Льюис Кэрролл ретінде танымал) 1883 жылғы жұмысына, ол бір рет өткізілетін спорт турнирлерінің стандартты дизайны екінші жақсы ойыншының екінші орынды жеңіп алуына кепілдік бермейтінін көрсеткеніне, сондай-ақ шамамен 1930 жылғы Хьюго Стейнхаус жұмысына байланыстырады, ол осы ойды дамытып, ойыншылардың ең аз ойында екінші орынды жеңіп алуына кепілдік беретін турнир дизайнын іздеді.
Quickselect was presented without analysis by Tony Hoare and first analyzed in a 1971 technical report by The first known linear time deterministic selection algorithm is the median of medians method, published in 1973 by Manuel Blum, Robert W. Floyd, Vaughan Pratt, Ron Rivest, and Robert Tarjan. They trace the formulation of the selection problem to work of Charles L. Dodgson (better known as Lewis Carroll) who in 1883 pointed out that the usual design of single elimination sports tournaments does not guarantee that the second best player wins second place, and to work of Hugo Steinhaus circa 1930, who followed up this same line of thought by asking for a tournament design that can make this guarantee, with a minimum number of games played (that is,