algorithm - O(n) - 按字典顺序排列的下一个排列

Question

我只是想知道这个算法的效率（O（n））是多少：

1. 找到满足 a[k] < a[k + 1] 的最大索引 k。如果不存在这样的索引，则排列是最后一个排列。
2. 找到最大的索引 l 使得 a[k] < a[l]。由于 k + 1 是这样一个索引，所以 l 是很好定义的并且满足 k < l。
3. 将 a[k] 与 a[l] 交换。
4. 反转从 a[k + 1] 到最后一个元素 a[n] 的序列。

据我了解，最坏的情况 O(n) = n （当 k 是前一个排列的第一个元素时），最好的情况 O(n) = 1 （当 k 是前一个排列的最后一个元素时）。

我可以说 O(n) = n/2 吗？

Answer 1

O(n) = n/2没有意义。让f(n) = n成为您的算法的运行时间。那么正确的说法f(n)就是 in O(n)。 O(n)是一组至多在 中渐近线性的函数n。

您的优化使预期的运行时间g(n) = n/2。 g(n)也在O(n)。事实上O(n) = O(n/2)，你节省的一半时间不会改变渐近复杂度。

Answer 2

算法中的所有步骤都是O(n)渐进的。

您的平均值不正确。仅仅因为最好的情况是 O(1) 而最坏的情况是 O(n)，你不能说算法需要 O(n)=n/2。大 O 表示法仅用于算法的上限。

所以算法仍然O(n)与最佳情况无关。

Answer 3

没有像 O(n) = n/2 这样的东西。

当您进行 O(n) 计算时，您只是想找到函数依赖关系，而不关心系数。所以没有 O(n)= n/2 就像没有 O(n) = 5n

Answer 4

渐近地，O(n) 与 O(n/2) 相同。在任何情况下，算法都是针对 n! 排列，因此顺序比您的估计要大得多（大约为 n！）。