Приложение 5. III. Оценки количества вычислительных операций в алгоритмах сокращения исходного описания по дискриминантному критерию (вторая задача)

1. Оптимальный (переборный) алгоритм. При сравнении всех вариантов по к из I параметров требуется С^k_I раз вычислить отношение (5. 3. 1) или вычислить 2С^k_I определителей k-го порядка. Учитывая, что для вычисления определителя k-го порядка требуется приблизительно k³/3 операций (см. [5. 14]), общее число операций равно

При больших значениях I для оценки числа операций воспользуемся приближенным соотношением. Учитывая асимптотическую формулу Стирлинга, получаем

(5.III.1)

2. Субоптимальный алгоритм. На i + 1-м шаге алгоритма требуется произвести (I - i) вычислений отношения (5. III. 1), что составляет приблизительно

операций. Количество вычислительных операций при сокращении числа параметров с I до к равно

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

(5.III.2)

Выигрыш в числе операций двух сравниваемых алгоритмов дается отношением (5. III. 1) к (5. III. 2). В предположении о том" что число параметров сокращается вдвое, это отношение приблизительно равно

3. Упрощенный алгоритм. В этом случае число операций, очевидно, не зависит от значения к и равно приблизительно

Выигрыш в числе операций по сравнению с предыдущим алгоритмом для больших значений I равен приблизительно 0,3 I.