Информатика • 11 класс
232

Оценка сложности вычислений

  • Сложность выполнения алгоритма оценивается по затраченному времени или занимаемому объёму памяти.
  • NP-полная (недетерминированно полиномиальная) задача — это задача из NP-класса, алгоритм решения которой находится за полиномиальное время.
  • NP-класс — класс задач, которые проверяются за полиномиальное время.

Сложность

Пояснение

Примеры

Константная O (1)

Время работы не зависит от количества элементов

Поиск элемента по индексу

Линейная O (n)

Время работы возрастает прямо пропорционально количеству элементов

Перебор элементов массива

Логарифмическая

O (log n)

Удвоение размера задачи увеличит время работы на постоянную величину

Бинарный поиск

Линеарифметическая O (n log n)

Удвоение размера входных данных увеличит время выполнения чуть более, чем вдвое

Сортировка слиянием или множеством

Полиномиальная

O (nk), где k = 1, 2, 3 …

Удвоение размера входных данных увеличивает время выполнения в 4 раза

Алгоритмы простой сортировки

Экспоненциальная kn, где k = 1, 2, 3 …

Увеличение размера задачи на 1 приводит к k-кратному увеличению необходимого времени

Алгоритмы перебора

Факториальная O (n!)

Время работы возрастает до астрономических пределов даже при небольшом увеличении набора данных

Алгоритмы комбинаторики

Было полезно?

Рекомендуем

Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках
Зарегистрироваться в «Облаке знаний»