Урок 20
§22. Сложность алгоритмов
Содержание урока
Как сравнивать алгоритмы?
Примеры вычисления сложности
Что такое асимптотическая сложность?
Выводы
Вопросы и задания
Выводы
• Временем работы алгоритма называется количество элементарных операций Т, выполненных исполнителем.
• Временная сложность алгоритма обычно зависит от объёма исходных данных N, например от размера массива.
• Пространственная сложность — это объём памяти, необходимой для работы алгоритма.
• Простой цикл, в котором количество шагов пропорционально N, — это алгоритм линейной сложности.
• Вложенный цикл, в котором количество шагов внешнего и внутреннего цикла пропорционально N, — это алгоритм квадратичной сложности.
• Алгоритм имеет асимптотическую сложность 0(f(N)), если найдётся такая постоянная с, что, начиная с некоторого N = N
0, выполняется условие T(N) ≤ с • f(N).
• Линейная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К раз.
• Квадратичная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К
2 раз.
Нарисуйте в тетради интеллект-карту этого параграфа.
Следующая страница Вопросы и задания
Cкачать материалы урока