Среднее время вычисления значений элементарных булевых функций

Рассматривается реализация дизъюнкции, конъюнкции и линейной функции, зависящих от растущего числа аргументов, неветвящимися программами с условной остановкой. Найдены асимптотически точные формулы для среднего времени вычисления значений этих функций. Установлено, что средние времена вычисления дизъюнкции и конъюнкции — постоянные величины, а среднее время вычисления линейной функции совпадает со сложностью реализации этой функции схемами из функциональных элементов.
Работа выполнена при поддержке Российского фонда фундаментальных исследований, проект 99–01–01175, и ФЦП “Интеграция”, проект 473.