По определению асимптотическая сложность алгоритма представляет собой скорость роста (во времени, пространстве или каком-либо другом ресурсе) в качестве размера увеличения входных данных.Лучше всего проанализировать сам алгоритм, чтобы определить эту скорость роста.Однако, если все, что у вас есть, это алгоритм сортировки «черного ящика», и вы знаете только размер входных данных и полученное время, лучшее, что вы можете сделать, - это проверить, не растет ли график входных данных и времени вшаблон, который будет выполнять конкретная функция.
Чтобы проверить эту идею, граф работает следующим образом:
- f (n) = n
- f (n) = n lnn
- f (n) = n ^ 2
и т. д., и посмотрите, какой из них больше всего напоминает график, созданный вами для времени запуска алгоритма.Помните, что асимптотический анализ в конечном итоге исключает как постоянные факторы для каждого члена, так и любые члены более низкого порядка.Итак, если ваш алгоритм все еще работает за линейное время, даже если график выглядит как f (n) = 2n, у вас все еще есть алгоритм O (n).