- Главная
- Разное
- Дизайн
- Бизнес и предпринимательство
- Аналитика
- Образование
- Развлечения
- Красота и здоровье
- Финансы
- Государство
- Путешествия
- Спорт
- Недвижимость
- Армия
- Графика
- Культурология
- Еда и кулинария
- Лингвистика
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Детские презентации
- Информатика
- История
- Литература
- Маркетинг
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Анализ сложности и эффективности алгоритмов. (Лекция 4) презентация
Содержание
- 1. Анализ сложности и эффективности алгоритмов. (Лекция 4)
- 2. Под трудоёмкостью алгоритма для данного конкретного
- 3. Основные понятия В самом широком смысле понятие
- 4. Критерии эффективности алгоритма: Временная эффективность (или временная
- 5. Трудоемкость основных алгоритмических конструкций в общем виде
- 6. Конструкция «Ветвление» Общая трудоемкость конструкции «Ветвление» требует
- 7. Конструкция «Цикл» После сведения конструкции к элементарным операциям ее трудоемкость определяется как:
- 11. Amin=0, при mах=x[1] Amax=n-1, при x[1]
- 12. Временная сложность алгоритма: Vmin=М1+М2+М3+М4+М5=1+N+(N-1)+0+(N-1)=3N-1 Vmax=М1+М2+М3+М4+М5=1+N+(N-1)+(N-1)+(N-1)=4N-2 Vср=М1+М2+М3+М4+М5=1+N+(N-1)+5/6+(N-1)=3N-0,16
- 13. Два класса алгоритмов: Экспоненциальные алгоритмы - алгоритмы
- 14. Время работы алгоритма удобно выражать в виде
- 15. Сравнение нескольких полиномиальных и экспоненциальных функций временной сложности
Под трудоёмкостью алгоритма для данного конкретного входа – (N), будем понимать количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе. Оценка функции трудоемкости алгоритма называется
Слайд 2
Под трудоёмкостью алгоритма для данного конкретного входа – (N), будем понимать
количество «элементарных» операций совершаемых алгоритмом для решения конкретной проблемы в данной формальной системе.
Оценка функции трудоемкости алгоритма называется сложностью алгоритма и позволяет определить предпочтения в использовании того или иного алгоритма для больших значений размерности исходных данных.
Оценка функции трудоемкости алгоритма называется сложностью алгоритма и позволяет определить предпочтения в использовании того или иного алгоритма для больших значений размерности исходных данных.
Слайд 3Основные понятия
В самом широком смысле понятие эффективности связано со всеми вычислительными
ресурсами, необходимыми для работы алгоритма.
В узком смысле под "самым эффективным" алгоритмом понимается самый быстрый.
Ограничения по времени является доминирующим фактором, определяющим пригодность конкретного алгоритма для практики.
В узком смысле под "самым эффективным" алгоритмом понимается самый быстрый.
Ограничения по времени является доминирующим фактором, определяющим пригодность конкретного алгоритма для практики.
Слайд 4Критерии эффективности алгоритма:
Временная эффективность (или временная сложность) программы по соответствующему алгоритму,
определяется временем, необходимым для ее выполнения.
Пространственная характеристика (емкость) измеряется количеством памяти, требуемой для выполнения программы соответствующего алгоритма.
Пространственная характеристика (емкость) измеряется количеством памяти, требуемой для выполнения программы соответствующего алгоритма.
Слайд 5Трудоемкость основных алгоритмических конструкций в общем виде сводится к следующим положениям:
Конструкция «Следование»
Трудоемкость конструкции есть сумма трудоемкостей блоков, следующих друг за другом.
Слайд 6Конструкция «Ветвление»
Общая трудоемкость конструкции «Ветвление» требует анализа вероятности выполнения переходов на
блоки «Then» и «Else» и определяется как:
Слайд 7Конструкция «Цикл»
После сведения конструкции к элементарным операциям ее трудоемкость определяется как:
Слайд 12Временная сложность алгоритма:
Vmin=М1+М2+М3+М4+М5=1+N+(N-1)+0+(N-1)=3N-1
Vmax=М1+М2+М3+М4+М5=1+N+(N-1)+(N-1)+(N-1)=4N-2
Vср=М1+М2+М3+М4+М5=1+N+(N-1)+5/6+(N-1)=3N-0,16
Слайд 13Два класса алгоритмов:
Экспоненциальные алгоритмы - алгоритмы "неэффективные" просто варианты полного перебора
Полиномиальные
алгоритмы – алгоритмы "эффективные", или "хорошие" алгоритмы, когда удается более глубоко проникнуть в суть решаемой задачи
Слайд 14Время работы алгоритма удобно выражать в виде функции от одной переменной,
характеризующей “размер” индивидуальной задачи, т.е. объем входных данных, требуемых для описания задачи
Экспоненциальный алгоритм называется алгоритм, у которого временная сложность равна Pn
Полиномиальным алгоритмом называется алгоритм, у которого временная сложность равна np
Экспоненциальный алгоритм называется алгоритм, у которого временная сложность равна Pn
Полиномиальным алгоритмом называется алгоритм, у которого временная сложность равна np
