Выводы по практическому применению алгоритмов
1. Субэкспоненциальные и экспоненциальные алгоритмы имеют практическое значение только при малых n (обычно при n <10).
2. При значительных значениях параметра n необходимо применять только полиномиальные алгоритмы.
3. При решении задач большой размерности по n необходимо использовать полиномиальные алгоритмы степени не выше 2–3.
4. При наличии нескольких алгоритмов одинаковой сложности для решения одной задачи следует выбирать алгоритмы с минимальной константой скорости роста.
Вопросы для проверки знаний.
1. Что называют сложностью алгоритма ?
2. Какие алгоритмы называют полиномиальными, экспоненциальными и субэкспоненциальными?
3. В чем отличие теорем 3.1 и 3.2 ?
4. Почему при значительных значениях параметра n необходимо применять только полиномиальные алгоритмы ?
Практические задания.
1. Необходимо выяснить, будет ли натуральное число n простым или составным. Разработать алгоритмы решения задачи, имеющие в худшем случае сложность по числу необходимых операций деления:
а) линейную по n,
б) меньшую, чем линейная.
2. Есть n одинаковых монет. Известно, что среди них – одна фальшивая, имеющая меньший вес. Также имеются двухчашечные весы, позволяющие сравнивать между собой любые веса.
Разработать алгоритмы поиска фальшивой монеты, имеющие в худшем случае сложность общего числа взвешиваний по n:
а) линейную,
б) меньшую, чем линейная.
Дата добавления: 2018-04-15; просмотров: 218; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!