Проблемът за изчисляване на статистическите данни за поръчка включва намирането на к-ти най-малкия елемент в поредицата от наш елементи. Този проблем понякога се нарича проблема с намирането на к-ти статистика на поръчката. Когато к = 1, проблемът се свежда до намиране на най-малкия елемент на последователност, и когато к = N, и най-големият елемент се постига в не повече от O (N) стъпки. Един от най-очевидните решения на проблема за изчисляване на статистически данни на последователност и е както следва: за организиране на оригиналната последователност, за да не се намалят елементите и отведе до втория елемент. В същото време, обаче, е необходимо да се вземат предвид изискванията на истинския проблем, който е в интерес на статистиката ред се изчисляват.
Първо, тя може да бъде, че в един подреден последователност на няколко ключови елементи (к-те, (к + 1) та.) ...] имат същата стойност. След това е необходимо да се вземе под внимание дали тези елементи следват един след друг в същия ред, както е в оригиналната последователност, или е по избор. В първия случай, подредбата на източника последователност трябва да изпълни един от методите за сортиране стабилен във втория случай е възможно да се използва всеки метод на сортиране.
На второ място. дали един или повече от статистиката на поръчката се търси. В зависимост от това може да бъде рентабилно използване на алгоритъм.
На трето място. избора на алгоритъм отразява броя на елементите п оригиналната последователност.
И накрая, ако оригиналната последователност трябва да се запази без промяна, за да намерите статистически ред ще трябва да се създаде копие на оригиналния последователност или набор от ключови елементи на оригиналната последователност. Използване ключ масив може да бъде полезно в случаите, когато елементите на оригиналната последователност имат сложна структура и техните промени в процеса на изчисляване структури последователност изискват значително време. Ако търсенето е стабилно сортиране не е необходимо, то е възможно да се използва рекурсивната процедура, базирана на бързасортировка Хоаре му (Quicksort), което осигурява най-бързите в средната сортиран.
За разлика от рекурсивни процедурата за намиране на к-ти статистика за поръчката от бързи процедури за сортиране Хоаре е, че, от една страна, след разделянето на две групи тази група е избрана в ko¬toroy е вторият елемент, и второ, да се нататъшна обработка само в тази група, но не и двете групи, както се прави в бързасортировка Хоаре му.
Времето, прекарано за намиране на к-тия метод за статистика, както този, и в друга, в зависимост от успешна селекция на еталонния елемент в разделянето на групи. Времето ще минимално, ако на всяка итерация групи съдържат около един и същ брой елементи. Доказано е, че когато всеки пропуск се извършва дори на снимачната площадка, съставляващи предходната 9/10, времето за изпълнение е от О на поръчката (н), а в най-лошия случай - не повече от O (N 2). А линеен метод за намиране на статистическите данни за поръчките осигурява най-лошия случай времето за изпълнение на поръчката O (N). Този метод се основава на намирането на "добра" и член на подпомагане се прилага за последователности с голям брой елементи.
Свързани статии