Кіріспе

Массивтегі k-шы ең кіші элементті табу алгоритмі

Компьютер ғылымында, quickselect – реттелмеген тізімдегі k-шы ең кіші элементті табуға арналған таңдау алгоритмі, сондай-ақ k-шы реттік статистика деп те аталады. Қатысты тез сұрыптау алгоритмі сияқты, ол Тони Хоармен әзірленген, сондықтан оны Хоардың таңдау алгоритмі деп те атайды. Тез сұрыптау сияқты, ол практикада тиімді және орташа жағдайда жақсы өнімділік көрсетеді, бірақ ең нашар жағдайда нашар жұмыс істейді. Quickselect және оның түрлері – тиімді нақты қолданыста қолданылатын таңдау алгоритмдері. Quickselect тез сұрыптаумен бірдей жалпы тәсілді қолданады, бір элементті тіреу нүктесі (pivot) ретінде таңдап, деректерді тіреу нүктесіне қатысты екіге бөледі, яғни тіреу нүктесінен кіші немесе үлкен деп бөлінеді. Алайда, тез сұрыптаудағыдай екі жаққа да рекурсия жасаудың орнына, quickselect тек бір жаққа ғана рекурсия жасайды – ізделіп отырған элементі бар жаққа. Бұл орташа күрделілікті азайтады , ал ең нашар жағдайда . Тез сұрыптау сияқты, quickselect әдетте орнында (in place) алгоритм ретінде іске асырылады, және k-шы элементті таңдаудан басқа, деректерді ішінара сұрыптайды. Сорттаумен байланысы туралы толыққанды талқылау үшін таңдау алгоритмін қараңыз.

Уақыт күрделілігі

Quicksort сияқты quickselect-тің де орташа өнімділігі жақсы, бірақ таңдалған півотқа сезімтал. Егер жақсы півоттар таңдалса, яғни іздеу жиынтығын белгілі бір үлеспен үнемі қысқартатын болса, онда іздеу жиынтығының мөлшері экспоненциалды түрде кемиді және индукция (немесе геометриялық қатарды қосу) арқылы орындалудың сызықтық екенін көруге болады, себебі әр қадам сызықтық және жалпы уақыт осының тұрақты есесінен шығады (іздеу жиынтығының қаншалықты жылдам қысқарғанына байланысты). Дегенмен, егер жаман півоттар үнемі таңдалса, мысалы, әр жолы бір ғана элементті қысқартатын болса, онда ең нашар жағдайда өнімділік квадраттық болады. Мұндай жағдай, мысалы, жиынның ең үлкен элементін іздеу кезінде, бірінші элементті півот ретінде пайдаланып, деректер сұрыпталған болса туындауы мүмкін. Алайда, кездейсоқ таңдалған півоттар үшін мұндай ең нашар жағдай өте сирек: кез келген жеткілікті үлкен тұрақты үшін салыстырудан артық пайдалану ықтималдығы , функциясы бойынша суперэкспоненциалды түрде кіші болады.

Нұсқалар

Ең оңай шешім – кездейсоқ осьтік элементті таңдау, бұл дерлік нақты сызықтық уақытты қамтамасыз етеді. Детерминистік тұрғыдан алғанда, 3 осьтік элементтің медианын қолдануға болады (quicksort сияқты), бұл нақты әлемде жиі кездесетін ішінара сұрыпталған деректерде сызықтық өнімділікті береді. Дегенмен, жасалған тізбектер ең нашар жағдайдағы күрделілікті тудыруы мүмкін; Дэвид Муссер осы стратегияға қарсы шабуылға мүмкіндік беретін "3 медиананы өлтіруші" тізбегін сипаттайды, бұл оның introselect алгоритмін жасауына түрткі болды. Күрделірек осьтік элементті таңдау стратегиясын қолдану арқылы ең нашар жағдайда да сызықтық өнімділікті қамтамасыз етуге болады; мұны медиан медианалары алгоритмі арқылы іске асыруға болады. Алайда, осьтік элементті есептеуге кететін шығын жоғары, сондықтан бұл әдетте практикада қолданылмайды. Жылдам орташа жағдай өнімділігі мен сызықтық ең нашар жағдай өнімділігін алу үшін негізгі quickselect-ті медиан медианаларымен біріктіруге болады; мұны introselect арқылы іске асыруға болады. Орташа уақыт күрделілігін егжей-тегжейлі есептеу кездейсоқ осьтік элементтер үшін ең нашар жағдайды көрсетеді (медиана жағдайында; басқа k мәндері үшін жылдамырақ). Тұрақты шама күрделірек осьтік элементті таңдау стратегиясы арқылы 3/2-ге дейін жақсартылуы мүмкін, бұл Floyd–Rivest алгоритмін береді, оның медиана үшін орташа күрделілігі бар, ал басқа k мәндері үшін жылдамырақ.