Задачи, которые сложно решить в общем случае, могут иметь простые решения, которые хорошо на практике работают во многих случаях. К примеру, Симплекс-метод имеет экспоненциальную сходимость в худшем случае, но во многих практических задачах, его время исполнения гораздо лучше (полиномиальная сходимость в среднем).
Если это допустимо в вашем случае, то вы можете померить фактические времена исполнения для доступных данных и оценить какая из моделей O(n), O(n2), O(n3) или O(log(n)) лучше описывает результаты.
К примеру, не сложно программно убедиться, какие из рассматриваемых алгоритмов являются O(1)
(для используемых данных):

Точки это измерения, а линии это соответствующие апроксимирующие полиномы.
Апроксимирующий полином вычисляется с помощью numpy.polyfit()
в make-figures.py
.
Вот таблица соответствия между log2(N)
полиномами на графике и соответствующими функциями роста:
|------------------------------+-------------------|
| Fitting polynom | Function |
|------------------------------+-------------------|
| 1.00 log2(N) + 1.25e-015 | N |
| 2.00 log2(N) + 5.31e-018 | N*N |
| 1.19 log2(N) + 1.116 | N*log2(N) |
| 1.37 log2(N) + 2.232 | N*log2(N)*log2(N) |
К примеру, измерения показывают, что слияние двух отсортированных списков это O(n) операция, если используется heapq.merge()
в Питоне (которая медленнее встроенного sort()
, который O(n * log n) в общем случае, но так как на входе два отсортированных массива, то timsort, используемый в Питоне лучше показывает результаты):

Конечно, измерения не всегда позволяют определить функцию роста:

См. пример кода как выполнить измерения, найти полиномы и построить графики в cdleary.py
и make-figures.py