Үлкен көлемді деректер үшін алгоритмдердің тиімділігінің өлшемі

Кіріспе

Үлкен кірістер үшін алгоритмнің жұмыс істеуін өлшеу

Компьютер ғылымында алгоритм, егер ол үлкен кірістер үшін ең нашар жағдайда ең жақсы алгоритмнен нашар тұрақты факторға (кіріс мөлшеріне тәуелсіз) орындаса, асимптотикалық оптимал деп аталады. Бұл үлкен O белгісін кеңінен қолдану нәтижесінде компьютерлік ғылым зерттеулерінде жиі кездесетін термин. Әлгідейрек айтқанда, алгоритм белгілі бір ресурсқа қатысты асимптотикалық оптималдық болып табылады, егер проблеманың осы ресурсты қажет ететіндігі Ω(f(n)) арқылы дәлелденсе және алгоритмнің тек O(f(n)) пайдалануы дәлелденсе. Бұл дәлелдеулер есептеудің белгілі бір моделін, яғни кіріс деректерімен рұқсат етілген операцияларға қатысты белгілі бір шектеулерді қажет етеді. Қарапайым мысал ретінде, барлық салыстыру сұрыптаулары орташа және ең нашар жағдайларда кем дегенде Ω(n log n) салыстыруды қажет ететіндігі белгілі. Mergesort және heapsort салыстыру сұрыптаулары, олар O(n log n) салыстыруларды орындайды, сондықтан олар осы мағынада асимптотикалық оптималды. Егер кіріс деректерінде салыстырудан басқа алгоритмдерді құруда пайдаланылатын кейбір априорлық қасиеттер болса, онда асимптотикалық жылдам алгоритмдер мүмкін болуы мүмкін. Мысалы, егер N нысандардың [1, N] ауқымындағы бүтін сандар екені белгілі болса, онда оларды O(N) уақыт ішінде, мысалы, сегменттеу арқылы сұрыптау мүмкін. Алгоритмнің асимптотикалық оптималдық болуының салдары болып табылады, жеткілікті үлкен кірістер үшін, ешқандай алгоритм оны тұрақты фактордан артық орындай алмайды. Осы себепті асимптотикалық оптималдық алгоритмдер көбінесе зерттеуде "жолының соңы" ретінде көрінеді, бұл нәтижеге қол жеткізуді күрт жақсартуға болмайды. Керісінше, егер алгоритм асимптотикалық жағынан оңтайлы болмаса, бұл кіріс көлемі өскен сайын алгоритмнің мүмкін болатын ең жақсы алгоритмнен нашар жұмыс істейтінін білдіреді. Іс жүзінде, тіпті асимптотикалық артықшылыққа ие болмаса да, жақсы жұмыс істейтін алгоритмдерді табу пайдалы. Жаңа алгоритмдер белгілі бір кіріспен жұмыс істеу, ресурстарды пайдаланудың төмендеуі немесе сипаттау мен іске асырудың қарапайым болуы сияқты артықшылықтарды да ұсына алады. Осылайша асимптотикалық оптималдық алгоритмдер әрқашан "сызықтың соңы" бола бермейді. Асимптотикалық оптималдық алгоритмдер маңызды теориялық нәтижелер болса да, асимптотикалық оптималдық алгоритм бірқатар практикалық жағдайларда қолданылмайтын болуы мүмкін: ол тек n үшін практикалық кіріс өлшемдерінің шегінен тыс жиі қолданылатын әдістерден артық, мысалы, кез-келген компьютерлік сақтау жүйесіне сыятын биттерден көп кіріс. Бұл өте күрделі, сондықтан оны дұрыс түсіну мен іске асырудың қиындығы қарастырылып отырған кіріс өлшемдерінің диапазонында оның ықтимал пайдасынан асып түседі. Іс жүзінде кездесетін кіріс ерекше жағдайларға жатады, олар тиімді алгоритмдерге ие немесе жаман ең нашар жағдай уақыттары бар эвристикалық алгоритмдер оны тиімді шеше алады. Қазіргі компьютерлерде жады кэшін және параллель өңдеу сияқты аппараттық оптимизациялар асимптотикалық оптималдық алгоритммен "бұзылуы" мүмкін (талдау осы аппараттық оптимизацияны ескермеді деп есептейміз). Бұл жағдайларда осы мүмкіндіктерді жақсы пайдаланатын және нақты деректердегі оңтайлы алгоритмнен артық болатын оңтайлы алгоритмдер болуы мүмкін. Асимптотикалық оптималдық алгоритмнің тәжірибеде қолданылмаған мысалы - Бернард Шазельдің қарапайым көпбұрыштарды үшбұрыштандыруға арналған сызықтық уақыт алгоритмі. Тағы бір - "Оптималды уақыт пен кеңістіктегі өлшемі өзгертілетін массивтер" деп жарияланған өлшемі өзгертілетін массивтер деректерінің құрылымы, ол тұрақты уақытта индекстеуге болады, бірақ көптеген машиналарда қарапайым массивтер индекстеумен салыстырғанда ауыр практикалық жазаны көтереді.

In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly encountered in computer science research as a result of widespread use of big O notation. More formally, an algorithm is asymptotically optimal with respect to a particular resource if the problem has been proven to require Ω(f(n)) of that resource, and the algorithm has been proven to use only O(f(n)). These proofs require an assumption of a particular model of computation, i. e., certain restrictions on operations allowable with the input data. As a simple example, it's known that all comparison sorts require at least Ω(n log n) comparisons in the average and worst cases. Mergesort and heapsort are comparison sorts which perform O(n log n) comparisons, so they are asymptotically optimal in this sense. If the input data have some a priori properties which can be exploited in construction of algorithms, in addition to comparisons, then asymptotically faster algorithms may be possible. For example, if it is known that the N objects are integers from the range [1, N], then they may be sorted O(N) time, e. g., by the bucket sort. A consequence of an algorithm being asymptotically optimal is that, for large enough inputs, no algorithm can outperform it by more than a constant factor. For this reason, asymptotically optimal algorithms are often seen as the "end of the line" in research, the attaining of a result that cannot be dramatically improved upon. Conversely, if an algorithm is not asymptotically optimal, this implies that as the input grows in size, the algorithm performs increasingly worse than the best possible algorithm. In practice it's useful to find algorithms that perform better, even if they do not enjoy any asymptotic advantage. New algorithms may also present advantages such as better performance on specific inputs, decreased use of resources, or being simpler to describe and implement. Thus asymptotically optimal algorithms are not always the "end of the line". Although asymptotically optimal algorithms are important theoretical results, an asymptotically optimal algorithm might not be used in a number of practical situations:
It only outperforms more commonly used methods for n beyond the range of practical input sizes, such as inputs with more bits than could fit in any computer storage system. It is too complex, so that the difficulty of comprehending and implementing it correctly outweighs its potential benefit in the range of input sizes under consideration. The inputs encountered in practice fall into special cases that have more efficient algorithms or that heuristic algorithms with bad worst case times can nevertheless solve efficiently. On modern computers, hardware optimizations such as memory cache and parallel processing may be "broken" by an asymptotically optimal algorithm (assuming the analysis did not take these hardware optimizations into account). In this case, there could be sub optimal algorithms that make better use of these features and outperform an optimal algorithm on realistic data. An example of an asymptotically optimal algorithm not used in practice is Bernard Chazelle's linear time algorithm for triangulation of a simple polygon. Another is the resizable array data structure published in "Resizable Arrays in Optimal Time and Space", which can index in constant time but on many machines carries a heavy practical penalty compared to ordinary array indexing.

Ресми анықтамалар

Формальды түрде, бізде проблеманы шешу үшін Ω(f(n)) уақыт қажет екенін көрсететін төменгі шек теоремасы бар делік, мұндағы n – инстанцияның (кірістің) өлшемі (Ω анықтамасын қараңыз). Онда мәселені O(f(n)) уақытында шешетін алгоритм асимптотикалық тұрғыдан оңтайлы деп аталады. Бұл шектер арқылы да айтуға болады: егер b(n) – орындалу уақытының төменгі шегі болса, ал берілген алгоритм t(n) уақыт алады десек, онда алгоритм асимптотикалық жағынан оңтайлы болады, егер:

Бұл шек, егер бар болса, әрқашан 1-ге тең немесе одан үлкен болады, себебі t(n) ≥ b(n). Көбінесе уақыт тиімділігіне қолданылса да, алгоритм асимптотикалық тұрғыдан оңтайлы кеңістік, кездейсоқ биттер, процессорлар саны немесе үлкен O нотациясы арқылы әдетте өлшенетін кез келген басқа ресурсты пайдаланады деп айтуға болады. Кейде нашар немесе жасырын болжамдар алгоритмнің асимптотикалық жағынан оңтайлы екендігін анықтауды қиындатады. Мысалы, төменгі шек теоремасы салыстыру сұрыптамаларындағы немесе жад ұйымдастырылуындағы сияқты, нақты абстрактілі машина моделін қабылдауы мүмкін. Осы болжамдарды бұзу арқылы жаңа алгоритм төменгі шек пен «асимптотикалық оңтайлы» алгоритмдерден асып түсуі мүмкін.

Жеделдету

Асимптотикалық түрде оптималды алгоритмнің болмауы жылдамдық деп аталады. Блумның жылдамдық туралы теоремасы, жылдамдыққа ие жасанды түрде құрастырылған мәселелердің бар екенін көрсетеді. Дегенмен, бүгінгі күні ең көп танымал алгоритмдердің асимптотикалық оптималдығы – ашық мәселе болып қалады. Мысалы, ең кішкентай қамтитын ағашты табуға арналған алгоритм бар, онда – Акерман функциясының өте баяу өсетін кері функциясы, бірақ белгілі ең төменгі шек – тривиалды шек. Бұл алгоритм асимптотикалық оптималды ма, әлі белгісіз, және егер оның оптималдығы нақтыланса, маңызды нәтиже деп есептелуі мүмкін. Копперсмит пен Виноград (1982) матрицалық көбейтудің алгоритмдердің шектеулі класында (лямбда есептеуімен Штрассендік билинеарлық теңдіктері) жылдамдықтың әлсіз түріне ие екенін дәлездеді.