Алгоритмы, структуры данных

       

Время работы алгоритма


Т.к. в оригинальном алгоритме флаг unvisited для каждого узла не может измениться более одного раза, то это означает, что алгоритм посещает каждый узел единожды, поэтому время его работы может быть оценено как O(N), где N – количество узлов.

Модифицированный алгоритм, как и исходный, посещает каждый узел представления программы единожды. В предельном (невозможном на практике) случае, однако, тип каждого узла может быть преобразован, поэтому время, необходимое для обработки одного узла может увеличиться. Тем не менее, время работы алгоритма также представляет собой величину порядка O(N).

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

Для сравнения предикатов можно использовать сравнения указателей на них (т.е. предикаты эквивалентны, если они указывают на один и тот же оператор ветвления) или алгоритм классификации выражений, описанный в [2]. Первый вариант позволяет выполнить сравнения без значительных затрат времени. Второй – позволяет найти одинаковые предикаты, которые не принадлежат одному оператору ветвления, но требует дополнительных затрат времени на классификацию предикатов.



Содержание раздела