Таким образом, оценки для сложности функций в разных базисах отличаются лишь постоянными множителями. В связи ... - Большая Энциклопедия Нефти и Газа
Выдержка из книги
Лупанов О.Б.
Кибернетический сборник Выпуск21
Таким образом, оценки для сложности функций в разных базисах отличаются лишь постоянными множителями. В связи с этим первоочередной задачей является определение главного множителя оценки - того, который не зависит от базиса. Под этим подразумевается, что вместо одной конкретной булевой функции рассматривается последовательность аналогичных ей функций, содержащая при каждом п чаще всего по одной функции от п переменных, а оценка ищется в виде произведения коэффициента, зависящего от базиса, на функцию от я, которая и представляет собой главный множитель.