Оптимальні програми

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

§3. Оцінка складності алгоритмів.

Під складністю алгоритму ми будемо розуміти сумарну складність операцій, що виконуються під час роботи алгоритму. Складність найбільш поширених операцій вважається такою:

•ввід та вивід елемента даних, присвоювання змінної - 1,

•запис на стек та зчитування зі стеку - 1,

•виклик процедури або функції - 1,

•умовний перехід (порівняння) - 1,

•виконання арифметичних чи логічних операцій - по кількості операцій,

•складність циклу рівна складності тіла циклу, помноженій на кількість повторів.

Введемо наступні означення. Ємністю арифметичної функції назвемо кількість дійсних (таких, що належать полю дійсних чисел) аргументів цієї функції. Всі натуральні і цілі числа надалі узагальнюємо до дійсних чисел. Наприклад: sign(x), (-x) - функції ємності 1, а - функція ємності 2. Якщо абстрагуватися від формату запису арифметичної функції, то можна сказати, що всі двохмісні алгебраїчні операції є функціями ємності 2. Приймаючи це до уваги, можемо сформулювати наступне твердження:

Твердження 3.

Кількість операндів у правильно записаному арифметичному виразі є числом, яке можна отримати, віднявши від сумарної ємності всіх функцій (операцій), що входять у вираз, кількість цих самих функцій і додавши одиницю:

К-сть операндів = сумарна ємність – к-сть функцій + 1.

Очевидно, що твердження 2 є узагальненням твердження 1, бо якщо вираз містить тільки двохмісні арифметичні операції, то сумарна ємність вдвічі більша за кількість функцій. Доводиться дане твердження аналогічно попередньому.

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

•критерій 1 - кількість машинних операцій, необхідних для обчислення виразу;

•критерій 2 - об’єм пам’яті, що використовується алгоритмом;

•критерій 3 - загальний час обробки виразу.

Критерії 1 та 3 дуже подібні між собою, проте не еквівалентні. Прогрес у мікроелектроніці привів до того, що сучасні комп’ютери, навіть ті, які мають лише один процесор, можуть виконувати декілька команд одночасно. Тому, виконуючи бодай часткове розпаралелювання обчислень, можна отримати суттєвий приріст швидкості виконання.