Презентация к уроку по теме «Алгоритмизация»

Презентации учебные
ppt
11.05.2018

Публикация педагогических разработок

Бесплатное участие. Свидетельство автора сразу.
Мгновенные 10 документов в портфолио.

Добавить материал

При использовании данной презентации при объяснении новой темы появляется возможность применять методы личностно-ориентированного обучения: проблемный метод, метод эвристической беседы и элементы исследования. Постановка проблемы ставит учащихся в условия, которые побуждают его решать учебную проблему, проводить анализ материала и оперировать им. Такая деятельность позволяет учащимся получить новую информацию, освоит новые способы применения знаний

sloshnost.ppt

Понятие сложности алгоритма

Для практики недостаточно знать, что задача алгоритмически разрешима. Т. к. ресурсы ЭВМ (ОП и время процессора) ограничены, следует выбирать из эквивалентных алгоритмов наиболее эффективный. Для оценки эффективности введено понятие сложности.

Оценка сложности зависит от  времени, затраченного на выполнение алгоритма  объема памяти, требуемой для хранения исходных данных задачи.

Временнáя сложность алгоритма это время T, необходимое зависимости от исходных для его выполнения в данных. T = k∙t, где k – колво вычислительных действий, t – время выполнения одного действия.

T(n) – зависимость времени от объема входных данных. n – это размерность задачи (для линейного массива – размер массива). Поведение T при увеличении n называется теоретической сложностью – O(f(n)).

Сравнительная оценка сложности алгоритмов Сложность Тип O(f(n)) O(n) зависимости Линейная O(n∙log2n) Логарифмическа я O(n2) O(n3) Полиномиальная Экспоненциальна Значение при n=210= =1024 1024 10240  10 6  10 9

Задача Дано: два алгоритма А1 и А2 , решающих одну и ту же задачу размерности n=10 6. А1 имеет сложность O1(n2) и выполняется на суперкомпьютере с быстродействием 10 8оп/с; А2 имеет сложность O2(n∙log2n) и выполняется на обычном компьютере с быстродействием 10 6оп/с. Требуется: найти время решения задачи t1 ?, t2 ?

Решение t1 = 10 12 / 10 8 = 10 4 с  2,8 ч t2 = 10 6 ∙log2 10 6 / 10 6 = 6 ∙log2 10  20 с Вывод: Разработка эффективных алгоритмов не менее важна, чем разработка быстрой электроники!

Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.

Посмотрите также