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

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

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

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

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

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

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

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

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

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

КД - кількість дужок (на стек попадають лише відкриваючі дужки, але ж їх потім звідти ще й забирають, тому операцій вдвічі більше);

КО - кількість операцій (кожна операція попадає на стек, знімається звідти і виводиться у вихідну послідовність);

КБ - кількість букв-ідентифікаторів (кожен ідентифікатор одразу виводиться);

ППО - порівняння пріоритетів операцій (перед тим, як занести операцію на стек, звідти видаляються операції з меншим пріоритетом).

Можна також дати наступні оцінки для розглядуваних величин:

КД  N/2 (не більше половини символів у виразі є дужками);

KO  N/2 (не більше половини символів є знаками операцій);

КБ  N/2 +1;

ППО  КО  N/2.

Звідси можемо зробити висновок, що загальна кількість операцій алгоритму ІТР має порядок 4N.

Для алгоритму POSTFIX має місце така формула:

К = N + 2*СЄ + КО,

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

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