Эффективность алгоритмов: временна́я сложность и сложность по памяти

Основы информатики

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

Введение в нотацию «Большое О»

Измеряет рост времени и памяти по мере увеличения входных данных
Примеры: $O(n)$, $O(n^2)$, $O(log\, n)$
«O» означает «порядок» роста, например O(n) = линейный

Временна́я сложность — офисная аналогия

График различных классов сложности в нотации «Большое О»

$O(1)$ – постоянное время – «Быстрый взгляд» – «константная»
$O(log\,n)$ – медленный рост времени – «Деление стопки» – «логарифмическая»
$O(n)$ – линейный рост – «Чтение документа» – «линейная»
$O(n\,log\,n)$ – ускоренный рост времени – «Сортировка стопки» – «линейно-логарифмическая»
$O(n^2)$ – квадратичный рост времени – «Сравнение документов» – «квадратичная»

Сложность по памяти — офисная аналогия

График различных классов сложности в нотации «Большое О»

$O(1)$ – постоянная память – «Рабочий стол» – «константная»
$O(log\,n)$ – медленный рост памяти – «Минимальные заметки» – «логарифмическая»
$O(n)$ – линейный рост – «Стикеры» – «линейная»
$O(n\,log\,n)$ – ускоренный рост памяти – «Временные стопки» – «линейно-логарифмическая»
$O(n^2)$ – квадратичный рост памяти – «Таблица сравнений» – «квадратичная»

Давайте потренируемся!

Основы информатики

Preparing Video For Download...