Авиационно инженерство Административно право Административно право Беларус Алгебра Архитектура Безопасност на живота Въведение в професията „психолог” Въведение в икономиката на културата Висша математика Геология Геоморфология Хидрология и хидрометрия Хидросистеми и хидравлични машини Културология Медицина Психология икономика дескриптивна геометрия Основи на икономически т Oria професионална безопасност Пожарна тактика процеси и структури на мисълта, Професионална психология Психология Психология на управлението на съвременната фундаментални и приложни изследвания в апаратура социалната психология социални и философски проблеми Социология Статистика теоретичните основи на компютъра автоматично управление теория на вероятностите транспорт Закон Turoperator Наказателно право Наказателно-процесуалния управление модерна производствена Физика Физични феномени Философски хладилни инсталации и екология Икономика История на икономиката Основи на икономиката Икономика на предприятията Икономическа история Икономическа теория Икономически анализ Развитие на икономиката на ЕС Спешни ситуации ВКонтакте Однокласници Моят свят Facebook LiveJournal Instagram
border=0

Сложност на алгоритъма

Нека разгледаме още една характеристика на алгоритъма - неговата сложност. Разработването и усъвършенстването на компютърните технологии доведе до създаването на различни алгоритми, които осигуряват решаването на многобройни приложни задачи, а дори и за еднотипни задачи са създадени много алгоритми (програми) (и се създават). Подобни алгоритми бяха наричани преди това еквивалентни. Въпреки това, за практика не е достатъчно да се знае, че решаването на даден проблем на компютъра по принцип е възможно (т.е. проблемът е алгоритмично решим). Изпълнението на всеки алгоритъм изисква определено количество компютърна памет, за да се приспособят данните и програмите, както и процесорното време за обработка на тези данни - тези ресурси са ограничени и следователно въпросът за ефективността на тяхното използване е легитимна. По този начин, в най-широк смисъл, понятието за ефективност е свързано с всички изчислителни ресурси, необходими за работата на алгоритъма. Обикновено под „най- ефективния” се разбира алгоритъмът, който осигурява най-бързи резултати, защото в практически ситуации именно сроковете често са доминиращият фактор, определящ пригодността на един алгоритъм. Поради тази причина времевата сложност на алгоритмите ще бъде обсъдена по-нататък.

Времето на работа на алгоритъма е удобно изразено като функция на една променлива, характеризираща "размера" на дадена задача, т.е. количеството входни данни, необходими за решаването му. Този подход е удобен, тъй като относителната сложност на задачите може да бъде оценена чрез нейния размер. Тъй като описанието на проблем, предназначен да бъде решен чрез изчислително устройство, може да се разглежда като дума с крайна дължина, представена от символи на крайна азбука, дължината на входната дума може да се приеме като формална характеристика на размера на проблема. Например, ако има задача за определяне на максималния брой в последователност от n елемента, тогава размерът на проблема ще бъде n , тъй като всеки вариант на входната последователност може да бъде определен с дума от n символа.

Времевата сложност на един алгоритъм е функция, която присвоява на всяка входна дължина на дума n максимума (за всички конкретни задачи със същата дължина n) времето, необходимо на алгоритъма да го реши.

В този случай, разбира се, се приема, че всички проблеми използват една и съща схема на кодиране на входните думи.

Различните алгоритми имат различна времева сложност и определянето на това коя от тях ще бъде достатъчно ефективна и която няма, се определя от много фактори. Въпреки това, теоретиците, участващи в разработването и анализа на алгоритми, за сравняване на ефективността на алгоритмите, предложиха прост подход за изясняване на ситуацията. Става дума за разликата между полиномни и експоненциални алгоритми.

Полиномът е алгоритъм, чиято времева сложност се изразява чрез определена полиномна функция на размера на проблема n.

Алгоритми, чиято времева сложност не се поддава на такава оценка, се наричат експоненциални.

Разликата между тези два вида алгоритми става особено забележима при решаване на проблеми с голям размер. За сравнение в таблицата. 7.2 показва данни за времето на решаване на задачи от различна сложност (данни, взети от книгата на М. Гари, Д. Джонсън [15, стр.20]) и съответстват на състоянието на развитието на изчислителната техника преди около двадесет години - това влияе на абсолютните стойности на времето за обработка, но относителните стойности за това няма да се промени).

От горните данни може да се види, че, първо, времето за обработка на експоненциалните алгоритми със същите размери на задачите (над 20) е много по-високо от това на полиноми; второ, скоростта на растеж на времето за обработка с нарастващ размер на задачите за експоненциалните алгоритми е значително по-висока, отколкото при полиноми.

Разликата между двата вида алгоритми е още по-убедителна, ако анализираме ефекта от увеличаване на скоростта на компютъра върху времето за изпълнение на алгоритъма. В раздела. 7.3 е показано колко нараства размерът на най-голямата задача за единица компютърно време, ако скоростта на компютъра се увеличи 100 и 1000 пъти.

От раздела. 7.3 може да се види, че например за експоненциален алгоритъм с функция на сложност f (n) = 2 n, увеличаването на скоростта на изчисление 1000 пъти води само до това, че размерът на най-големия проблем се увеличава само с 10 единици, докато за функцията f (n) ) = n 5 увеличава се почти 4 пъти.

Таблица 7.2.

Таблица 7.3.

Дадените примери имат за цел да покажат, че точно както има алгоритмично неразрешими проблеми, съществуват обективно сложни проблеми, т.е. такива, сложността на които не може да бъде намалена чрез подобряване на компютъра. Задача се счита за трудна за решаване, ако не е възможно да се построи полиномиален алгоритъм за него. Това твърдение не е категорично, тъй като съществуват известни проблеми, при които експоненциалните алгоритми работят доста ефективно. Пример за това е симплексният метод, който успешно се използва при решаване на задачи за линейно програмиране, имащ функция на сложност f (n) = 2 n . Въпреки това, няма много примери от този вид и ситуацията трябва да бъде призната като обща: полиномни алгоритми с функции на сложност n, n 2 или n 3 . Например, при решаване на проблема с намирането на желаните данни от тези в най-лошия случай, сложността е n ; ако се изчисли средната интензивност на труда (продължителност на търсене), тя ще бъде (n + 1) / 2 - в двата случая функцията на сложност се оказва линейна . подреждане в даден ред и подобни данни води до полином от 2-ра степен; сложността на задачата за изчисляване на детерминанта на система от η линейни уравнения с n неизвестни се характеризира с полином от трета степен. Подобряването на производителността на компютърните елементи намалява времето за изпълнение на алгоритъма, но не намалява степента на сложност на полинома. Следователно решаването на практически проблем на компютъра трябва да бъде предшествано от оценка на неговата сложност и доказателство, че проблемът е решен в разумен срок.





Вижте също:

Пример 4.6

Рекурсивни функции

Струнен вербален алгоритъм

Естествени и изкуствени системи

Условна ентропия

Връщане към съдържанието: Теоретични основи на компютърните науки

2019 @ ailback.ru