Я написал алгоритм поиска грубой силы для проблемы коммивояжера и протестировал его, чтобы увидеть время, которое требуется для разных номеров "городов". Из графика ниже видно, что время примерно пропорционально (n-1)!
, где n
- число "городов". Он не прямо пропорционален n!
(в конце концов, (n-1)! = n! / n
).
Мой вопрос в том, правильно ли сказать, что алгоритм работает в O(n!)
, или мне лучше сказать O((n-1)!)
? Я никогда раньше этого не видел, но он кажется более точным. Кажется, я что-то неправильно понял.
[t = время, n = количество городов]