Сложность вычислительных алгоритмов обычно определяется по двум критериям: время выполнения и объём используемой памяти. 1

Временная сложность — это количество операций, которые должен выполнить алгоритм. 1 Она показывает, как растёт время выполнения алгоритма при увеличении входных данных. 1

Пространственная сложность алгоритма измеряет объём памяти, которую он использует в зависимости от размера входных данных. 1 На пространственную сложность влияют несколько факторов, включая количество переменных, тип и размер структуры данных, вызовы функций и способ выделения памяти. 1

Для оценки сложности алгоритмов используют различные нотации, например:

• O описывает оценку сложности сверху, то есть максимальное количество операций, которое алгоритм может выполнить в худшем случае. 4 Например, O(n) означает, что сложность алгоритма растёт линейно. 4
• Ω описывает оценку сложности снизу, то есть минимальное количество операций, которое алгоритм будет выполнять в лучшем случае. 4 Например, Ω(n) означает, что сложность растёт так же или быстрее, чем линейно. 4
• Θ описывает плотную оценку алгоритма. 4 В скобках после ϴ указывают функцию, которая ограничивает сложность как сверху, так и снизу. 4

Также для оценки сложности алгоритмов используют метод Монте-Карло: алгоритм запускают на случайных данных разного размера, замеряют время и память. 3 Полученные измерения выкладывают на отдельные графики для памяти и времени, а затем автоматически вычисляют функцию, которая лучше всего описывает полученное облако точек. 3