На этом шаге мы разберем, что представляет собой временнАя сложность вычислений.
ВременнАя сложность алгоритма - это теоретическая оценка времени или количества операций, необходимых для решения задачи. (В примере 3.1 приведён простой способ оценки времени выполнения кода с помощью модуля time языка Python.)
Пример 3.1. Вычисление времени выполнения кода с помощью модуля time
| 1 2 3 4 5 6 |
import time t = time.time() # вставьте сюда некоторый код elapsed_time = time.time() - t print(elapsed_time) |
Временная сложность определяется некоторой функцией T(), зависящей от исходного размера задачи и подсчитывающей количество операций для выполнения конкретной задачи. В информатике эффективность алгоритмов обычно определяется поведением функции T() при достаточно больших размерах задачи. Более того, ключевым фактором становится скорость роста функции T() при стремлении размера задачи к бесконечности. В последующих шагах рассматриваются именно эти темы, а также математический аппарат, используемый обычно для оценки временнОй сложности вычислений. Несмотря на то что временная сложность алгоритмов решения задач может зависеть от многих факторов, здесь мы ограничимся её зависимостью лишь от одного фактора - размера задачи.
На следующем шаге мы рассмотрим порядок роста функций.
