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

Question

我只是想知道 this algorithm 的效率 (O(n)) 是多少？ :

1. 找到最大的索引 k 使得 a[k] < a[k + 1]。如果不存在这样的索引，则排列是最后一个排列。
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)在O(n)中。 O(n) 是一组在 n 中最多渐近线性的函数。

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