search

lydrainbowcat / tedukuri

《算法竞赛进阶指南》资源社区
2.35k stars 601 forks source link

CH0103 暴力的复杂度应为 O(n*(n-2)!) 而非 O(n*n!) #66

Closed JeffersonQin closed 2 years ago

JeffersonQin commented 2 years ago

如题。起点和终点固定，只需枚举剩下的 n-2 个点的全排列，而且O(n!)应该与O((n-2)!)不等价。

lydrainbowcat commented 2 years ago

O((n-2)!)更紧，但是大O表示为O(n!)也没什么大问题

这里主要是突出一个枚举排列的时间复杂度是阶乘级别，下一版会考虑修订一下

JeffersonQin commented 2 years ago

好的，感谢回复