Часть 01 — «Теория без практики так же неполна, как и практика без теории». — Курт Левин
Прежде всего, что такое временная сложность? Представьте, что у вас есть коробка из-под обуви, полная бейсбольных карточек, и ваша миссия — найти в этой коробке конкретную карточку. Если вы начнете поиск случайным образом, выбирая по одной карте за раз, поиск может занять много времени. Это происходит потому, что вам нужно проверять каждую карту, пока не найдете нужную. Пока все хорошо, верно?
Временная сложность — это то, как мы измеряем время, необходимое для решения задачи, например, для поиска карточки в коробке. Проще говоря, мы можем сказать, что это мера того, насколько быстро или медленно может выполняться задача.
Существуют разные способы классификации временной сложности, давайте поговорим о двух из них.
Линейная временная сложность
Время, необходимое для решения проблемы, увеличивается пропорционально ее размеру.
Например, если у вас в коробке в два раза больше карт, поиск нужной карты займет примерно в два раза больше времени. Это как проверять каждую карту по очереди.
Квадратичная временная сложность
Время, необходимое для решения проблемы, увеличивается квадратично с размером проблемы.
Это означает, что если у вас в два раза больше ящиков, поиск нужной карты займет примерно в четыре раза больше времени. Это как проверять каждую пару карточек, чтобы убедиться, что вы нашли правильную.
Чем выше временная сложность, тем больше времени потребуется на поиск решения.
