На практиці нам потрібні не просто алгоритми, а хороші алгоритми в широкому сенсі цього слова. Одним з критеріїв якості алгоритму є час, необхідний для його виконання; дану характеристику можна оцінити по тому, скільки разів виконується кожен крок. Іншими критеріями є адаптованість алгоритму до різних комп'ютерів, його простота, витонченість і т. д.
Д. Кнут, Мистецтво програмування
Книга 1. Основні алгоритми
1.1. АЛГОРИТМИ
Попередня публікація
...
На практиці нам потрібні не просто алгоритми, а хороші алгоритми в широкому сенсі цього слова. Одним з критеріїв якості алгоритму є час, необхідний для його виконання; дану характеристику можна оцінити по тому, скільки разів виконується кожен крок. Іншими критеріями є адаптованість алгоритму до різних комп'ютерів, його простота, витонченість і т. д.
Часто вирішити одну і ту ж проблему можна за допомогою декількох алгоритмів і потрібно вибрати найкращий з них. Таким чином, ми потрапляємо у надзвичайно цікаву і вкрай важливу область аналізу алгоритмів. Предмет цієї області полягає в тому, щоб для заданого алгоритму визначити робочі характеристики.
Як приклад давайте дослідимо з цієї точки зору алгоритм Евкліда. Припустимо, нам потрібно вирішити наступну задачу: "Нехай задано значення n, а m може бути будь-яким цілим позитивним числом. Тоді чому одно середнє число Тn виконань кроку E1 алгоритму Е?". Перш за все необхідно переконатися в тому, що завдання має сенс, оскільки ми маємо знайти середнє при нескінченно великій кількості значень m. Але цілком очевидно, що після першого кроку El значення буде мати тільки залишок від ділення m на n.Тому все, що ми повинні зробити для знаходження значення Тn, - це випробувати алгоритм для m = 1, m = 2, ..., m = n, підрахувати сумарне число виконань кроку El і розділити його на n.
А тепер розглянемо ще одне важливе питання, що стосується поведінки Тn як функції від n: чи можна її апроксимувати, наприклад, функцією 1*n/3 або √n? Насправді це надзвичайно складна і цікава математична проблема, яка ще не вирішена остаточно; більш докладно вона буде розглянута в розділі 4.5.3. Можна довести, що при великих значеннях n Тn веде себе, як функція (l2 (ln 2) / π2) ln n, тобто вона пропорційна натуральному логарифму n. Зауважимо, що коефіцієнт пропорційності не можна просто взяти і вгадати; щоб визначити його, потрібно затратити певні зусилля. Більш докладно про алгоритм Евкліда, а також про інші способи обчислення найбільшого загального дільника буде говоритися в розділі 4.5.2.
Для визначення області подібних досліджень автор використовує термін аналіз алгоритмів. Основна ідея полягає в тому, щоб взяти конкретний алгоритм і визначити його кількісні характеристики. Час від часу ми будемо також з'ясовувати, чи є алгоритм оптимальним у певному сенсі. Теорія алгоритмів - це зовсім інша область, в якій, в першу чергу, розглядаються питання існування чи не існування ефективних алгоритмів обчислення визначених величин.
Продовження
До цих пір наше обговорення алгоритмів носило досить загальний характер, і, ймовірно, "математично налаштований" читач утвердився в думці, що всі попередні коментарі представляють собою дуже хиткий фундамент для побудови будь-якої теорії алгоритмів.Тому давайте підіб'ємо підсумок даного розділу, коротко описавши метод, за допомогою якого поняття алгоритму можна строго обгрунтувати в термінах математичної теорії множин.
На практиці нам потрібні не просто алгоритми, а хороші алгоритми в широкому сенсі цього слова. Одним з критеріїв якості алгоритму є час, необхідний для його виконання; дану характеристику можна оцінити по тому, скільки разів виконується кожен крок. Іншими критеріями є адаптованість алгоритму до різних комп'ютерів, його простота, витонченість і т. д.
Досі ми говорили про форму запису алгоритмів, а тепер давайте спробуємо виконати один з них. Хочу відразу зауважити, що читачеві не слід розраховувати на те, що алгоритми можна читати, як роман.Таке читання приведе до того, що вам буде важко зрозуміти, що ж насправді відбувається при виконанні алгоритму. Для перевірки алгоритму, в ньому треба розібратися, і кращий спосіб зрозуміти, як він працює, - випробувати його.
ПОНЯТТЯ алгоритм є основним для всієї галузі комп'ютерного програмування, тому розпочати ми повинні з ретельного аналізу цього терміну.
Фундаментальна монографія відомого американського математика і фахівця в галузі комп'ютерних наук Дональда Кнута, присвячена розгляду та аналізу найважливіших алгоритмів, що використовуються в інформатиці. У 1999 році книга була визнана однією з дванадцяти кращих фізико-математичних монографій століття