Кіріспе
Алгоритмдердің ресурстарды қаншалықты тиімді пайдалануының өлшемі. Компьютер ғылымында, берілген алгоритмнің ең жақсы, ең нашар және орташа жағдайлары ресурстарды пайдаланудың тиесілі, ең көп және орташа деңгейін көрсетеді. Әдетте қарастырылатын ресурс – орындалу уақыты, яғни уақыт күрделілігі, бірақ ол жад немесе басқа да ресурс болуы мүмкін. Ең жақсы жағдай – n элементтен тұратын кіріс деректеріне қатысты ең аз қадамдарды орындайтын функция. Ең нашар жағдай – n өлшемді кіріс деректеріне қатысты ең көп қадамдарды орындайтын функция. Орташа жағдай – n элементтен тұратын кіріс деректеріне қатысты қадамдардың орташа санын орындайтын функция. Нақты уақытты есептеуде ең нашар жағдайдағы орындалу уақыты ерекше маңызды, себебі алгоритмнің әрқашан уақтылы аяқталуын қамтамасыз ету үшін ең нашар жағдайда қанша уақыт қажет болатынын білу қажет. Орташа көрсеткіштер және ең нашар жағдайдағы көрсеткіштер алгоритмді талдауда ең көп қолданылады. Ең жақсы жағдайдағы көрсеткіштер кеңінен таралмаған, бірақ олардың да пайдасы бар: мысалы, жекелеген тапсырмалардың ең жақсы жағдайлары белгілі болғанда, оларды жалпы ең нашар жағдайды талдаудың дәлдігін арттыру үшін қолдануға болады. Компьютер ғалымдары күтілетін орындалу уақытын анықтау үшін ықтималдық талдау әдістерін, әсіресе күтілетін мәнді пайдаланады. Бұл терминдер басқа да контекстерде қолданылады; мысалы, эпидемияның ең нашар және ең жақсы жағдайлары, электрондық тізбек элементінің ең нашар температурасы және т.б. Егер белгілі бір толеранттылыққа ие компоненттер қолданылса, құрылғылар толеранттылық пен сыртқы жағдайлардың ең нашар комбинациясында да дұрыс жұмыс істеуі тиіс.
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is at least, at most and on average, respectively. Usually the resource being considered is running time, i. e. time complexity, but could also be memory or some other resource. Best case is the function which performs the minimum number of steps on input data of n elements. Worst case is the function which performs the maximum number of steps on input data of size n. Average case is the function which performs an average number of steps on input data of n elements. In real time computing, the worst case execution time is often of particular concern since it is important to know how much time might be needed in the worst case to guarantee that the algorithm will always finish on time. Average performance and worst case performance are the most used in algorithm analysis. Less widely found is best case performance, but it does have uses: for example, where the best cases of individual tasks are known, they can be used to improve the accuracy of an overall worst case analysis. Computer scientists use probabilistic analysis techniques, especially expected value, to determine expected running times. The terms are used in other contexts; for example the worst and best case outcome of an epidemic, worst case temperature to which an electronic circuit element is exposed, etc. Where components of specified tolerance are used, devices must be designed to work properly with the worst case combination of tolerances and external conditions.
Алгоритмнің ең жақсы орындалуы
Компьютерлік ғылымда "ең жақсы жағдайдың өнімділігі" термині алгоритмнің оңтайлы жағдайлардағы жұмысын сипаттау үшін қолданылады. Мысалы, тізімдегі қарапайым сызықты іздеу үшін ең жақсы жағдай, ізделіп жатқан элемент тізімнің бірінші элементі болғанда туындайды. Алгоритмдерді әзірлеу және таңдау сирек жағдайларда ғана ең жақсы жағдайдың өнімділігіне негізделеді: академиялық және коммерциялық ұйымдардың көпшілігі орташа жағдайдың күрделілігі мен ең нашар жағдайдың өнімділігін жақсартуға көбірек қызығушылық танытады. Алгоритмдерді шектеулі жиындығы бар кіріс мәліметтері үшін нақты шешімдерді енгізу арқылы ең жақсы жағдайда жұмыс істеу уақытын жақсартуға оңай болады, бірақ бұл өлшемді дерлік мәнсіз етеді.
Іс жүзіндегі салдарлары
Көптеген алгоритмдер ең нашар жағдайда нашар жұмыс істейді, бірақ орташа жағдайда жақсы жұмыс істейді. Шешуге тырысатын мәселелер үшін бұл жақсы жаңалық: бізге қызықты жағдайлар орташа екендігіне үміттенуге болады. Криптография үшін бұл өте жаман: криптографиялық мәселенің әдеттегі жағдайлары қиын болуын қалаймыз. Мұнда, кездейсоқ өзін-өзі азайту сияқты әдістерді кейбір нақты мәселелер үшін ең нашар жағдайдың орташа жағдайдан қиын емес екенін, немесе, теңдесінше, орташа жағдайдың ең нашар жағдайдан оңай емес екенін көрсету үшін қолдануға болады. Екінші жағынан, хэш-кестелер сияқты кейбір дерек құрылымдарының өте нашар жағдайлары болады, бірақ жеткілікті мөлшердегі және дұрыс жазылған хэш-кесте статистикалық түрде ең нашар жағдайды көрсетпейді; орындалған операциялардың орташа саны экспоненциалдық төмендеу қисығымен өтеді, сондықтан операцияның орындалу уақыты статистикалық түрде шектеледі.