Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

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

1. Оптимальный (переборный) алгоритм. При сравнении всех вариантов по к из I параметров требуется СkI раз вычислить отношение (5. 3. 1) или вычислить 2СkI определителей k-го порядка. Учитывая, что для вычисления определителя k-го порядка требуется приблизительно k3/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.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"