algorithm - O(n) - 辞書式の次の順列

Question

このアルゴリズムの効率 (O(n)) とは何か疑問に思っています:

1. a[k] < a[k + 1] となる最大のインデックス k を見つけます。そのようなインデックスが存在しない場合、順列は最後の順列です。
2. a[k] < a[l] となる最大のインデックス 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)、時間の半分を節約しても、漸近的な複雑さは変わりません。

Answer 2

アルゴリズムのすべてのステップはO(n)漸近的に行われます。

あなたの平均化は正しくありません。最良のケースが O(1) で、最悪のケースが O(n) であるという理由だけで、アルゴリズムが O(n)=n/2 を取るとは言えません。Big O 表記は、単にアルゴリズムの上限を表すものです。

そのため、アルゴリズムはO(n)最良のシナリオに関係ありません。

Answer 3

O(n) = n/2 というものはありません。

O(n) 計算を行うときは、関数の依存関係を見つけようとしているだけで、係数は気にしません。つまり、O(n) = 5n がないのと同じように、O(n)= n/2 はありません。

Answer 4

漸近的に、O(n) は O(n/2) と同じです。いずれにせよ、アルゴリズムは n! のそれぞれに対して実行されます。順列なので、次数は推定よりもはるかに大きくなります (n! の次数)。