Оптимальні програми обчислення виразів, Детальна інформація

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

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



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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ввівши необхідні нам поняття, ми можемо перейти до оцінки різних алгоритмів згідно вказаних критеріїв.

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

алгоритм переводу виразу в префіксну форму є еквівалентним за складністю алгоритму ITP (інфіксна в постфіксну - §1);

алгоритм обчислення виразу в префіксній формі є еквівалентний за складністю алгоритму POSTFIX (див. твердження 2, §1);

алгоритм POSTFIX більш зручний для реалізації.

Тоді нам залишається розглянути тільки алгоритми обчислення виразу безпосередньо в інфіксній формі та обчислення за допомогою переведення в постфіксну форму.

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

К = N + КД + КО * 3 + КБ + ППО ,

де N - кількість операцій порівняння символів (визначення наступного символу послідовності);