Урок 39
§22. Сложность алгоритмов

Содержание урока

Как сравнивать алгоритмы?

Примеры вычисления сложности

Что такое асимптотическая сложность?

Выводы

Вопросы и задания

Выводы

• Временем работы алгоритма называется количество элементарных операций Т, выполненных исполнителем.
• Временная сложность алгоритма обычно зависит от объёма исходных данных N, например от размера массива.
• Пространственная сложность — это объём памяти, необходимой для работы алгоритма.
• Простой цикл, в котором количество шагов пропорционально N, — это алгоритм линейной сложности.
• Вложенный цикл, в котором количество шагов внешнего и внутреннего цикла пропорционально N, — это алгоритм квадратичной сложности.
• Алгоритм имеет асимптотическую сложность 0(f(N)), если найдётся такая постоянная с, что, начиная с некоторого N = N₀, выполняется условие T(N) ≤ с • f(N).
• Линейная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К раз.
• Квадратичная сложность означает, что при увеличении размера массива в К раз количество операций увеличивается примерно в К² раз.

Нарисуйте в тетради интеллект-карту этого параграфа.

Следующая страница Вопросы и задания

Cкачать материалы урока