Tema ocenka_slozhnosti_algoritmov ЛІКТ 590

В інформатиці, теорія складності обчислень є розділом теорії обчислень, що вивчають вартість роботи, необхідної для вирішення обчислювальної проблеми. Вартість зазвичай вимірюється абстрактними поняттями часу і простору, званими обчислювальними ресурсами. Час визначається кількістю тривіальних кроків, необхідних для вирішення проблеми, тоді як простір визначається об'ємом пам'яті або місця на носії даних. Таким чином, в цій області робиться спроба відповісти на центральне питання розробки алгоритмів: «як зміниться час виконання і обсяг використаної пам'яті в залежності від розміру входу 1) і виходу 2)?».

Зокрема, теорія складності обчислень визначає NP- повні задачі, які недетермінірованного машина Тьюринга може вирішити за поліноміальний час, тоді як для детермінованої машини Тьюринга поліноміальний алгоритм невідомий.

Кількість елементарних операцій, витрачених алгоритмом для вирішення конкретного екземпляра задачі, залежить не тільки від розміру вхідних даних, але і від самих даних. Наприклад, кількість операцій алгоритму сортування вставками значно менше в разі, якщо вхідні дані вже відсортовані. Щоб уникнути подібних труднощів, розглядають поняття тимчасової складності алгоритму в гіршому випадку.

Тимчасова складність алгоритму (в гіршому випадку) - це функція розміру вхідних і вихідних даних, що дорівнює максимальній кількості елементарних операцій, що проробляються алгоритмом для вирішення примірника завдання зазначеного розміру. У багатьох задачах розмір виходу не перевищує або пропорційний розміру входу - в цьому випадку можна розглядати тимчасову складність як функцію розміру тільки вхідних даних.

Просторова складність алгоритму (в гіршому випадку) - це функція розміру вхідних і вихідних даних, що дорівнює максимальній кількості витраченої пам'яті, витраченої алгоритмом для вирішення примірника завдання зазначеного розміру. У багатьох задачах розмір виходу не перевищує або пропорційний розміру входу - в цьому випадку можна розглядати просторову складність як функцію розміру тільки вхідних даних.

Незважаючи на те, що функція часової складності алгоритму в деяких випадках може бути визначена точно, в більшості випадків шукати точне її значення безглуздо. Справа в тому, що, по-перше, точне значення тимчасової складності залежить від визначення елементарних операцій (наприклад, складність можна вимірювати в кількості арифметичних операцій або операцій на машині Тьюринга), а по-друге, при збільшенні розміру вхідних даних вклад постійних множників і доданків нижчих порядків, які фігурують в вираженні для точного часу роботи, стає вкрай незначним.

Асимптотична складність - розгляд вхідних даних великого розміру і оцінка порядку зростання часу роботи алгоритму. Зазвичай алгоритм з меншою асимптотичної складністю є більш ефективним для всіх вхідних даних, за винятком лише, можливо, даних малого розміру.

Для запису асімтотіческой складності алгоритмів використовуються наступні позначення:

Якщо створювана програма буде використана тільки кілька разів, тоді вартість написання і налагодження програми буде домінувати в загальній вартості програми. В цьому випадку слід віддати перевагу алгоритм, найбільш простий для реалізації.

Якщо програма буде працювати тільки з «малими» вхідними даними, то ступінь зростання часу виконання матиме менше значення, ніж константа, присутня у формулі часу виконання. Разом з тим і поняття «дрібниці» вхідних даних залежить від точного часу виконання конкуруючих алгоритмів. Існують алгоритми, такі як алгоритм цілочисельного множення, асимптотично найефективніші, але які ніколи не використовують на практиці навіть для великих завдань, так як їх константи пропорційності значно перевищують аналогічні константи інших, більш простих і менш «ефективних» алгоритмів.

Ефективні, але складні алгоритми можуть бути небажаними, якщо готові програми будуть підтримувати особи, які беруть у написанні цих програм.

Відомо кілька прикладів, коли ефективні алгоритми вимагають таких великих обсягів машинної пам'яті (без можливості використання більш повільних зовнішніх коштів зберігання), що цей фактор зводить нанівець перевагу «ефективності» алгоритму.

У численних алгоритмах точність і стійкість алгоритмів не менш важливі, ніж їх тимчасова ефективність.

Клас P вміщує всі ті проблеми, вирішення яких вважається «швидким», тобто полиномиально залежать від розміру входу. Так само як сортування, пошук у безлічі, з'ясування зв'язності графів і багато інших.

Клас NP містить завдання, які недетермінірованного машина Тьюринга в змозі вирішити за поліноміальний кількість часу. Слід зауважити, що недермінірованним машина Тьюринга є лише абстрактною моделлю, в той час як сучасні комп'ютери відповідають детермінованою машини Тьюринга з обмеженою пам'яттю. Таким чином, клас NP включає в себе клас P, а також деякі проблеми, для вирішення яких відомі лише алгоритми, експоненціально залежать від розміру входу (тобто неефективні для великих входів). В клас NP входять багато знаменитих проблеми, такі як задача комівояжера, задача здійсненності булевих формул, факторизація і ін.

якщо при збільшенні розміру вхідного масиву в 2 рази кількість ітерацій алгоритму за його обробці зросте в 4 рази, то це - квадратична залежність.

Можна цю функцію отримати і експериментально - потрібно просто заміряти час роботи алгоритму на різних обсягах вхідних даних і побудувати графік.

Може виявитися, що алгоритм з більшою трудомісткістю буде більш ефективний на невеликих обсягах даних, оскільки коефіцієнти при її розрахунку зазвичай опускаються і вважається гранична оцінка при. Наприклад, алгоритм буде явно ефективніше на невеликих обсягах, ніж. Тому Вам, можливо, буде цікавіше заміряти реальну продуктивність і отримати графічну залежність експериментально.

1) довжина опису даних завдання в бітах

2) довжина опису рішення задачі