ヒープのアルゴリズム時間の複雑度

誰でも私にこのヒープのアルゴリズムの時間複雑さが正確に何であるか教えてもらえますか？https://en.wikipedia.org/wiki/Heap%27s_algorithm？ヒープのアルゴリズム時間の複雑度

私はいくつかのウェブサイトを検索しましたが、回答はすべて曖昧です。時間の複雑さはO（N！）であり、O（NlogN）というものもあります。正しいのはどちらですか？なぜ？

ありがとうございます。

2017-03-18 USER1223_T

N！すべての順列とすべてを生成するには、Θ（N！）の時間とΘ（N）の空間が必要です。換言すれば、各置換は償却されたΘ（1）時間を必要とする。

これらの事実は、Wikipediaのページに示されている再帰アルゴリズムから導くことができます。本質的に、コードはスワップとアウトプットを交互にして、各アウトプットが1回のスワップを含むようにします。

しかし、呼び出し操作とループテストもあります。各コールの前に単一のループテストが存在するため、コールの総数を数えるだけで済みます。

最悪の場合、出力前にn再帰呼び出しがあります。しかし、それはアルゴリズムの冒頭で一度だけ起こります。引数がnの単一コールでは、nが生成されます。出力する。 n再帰呼び出しでは、それぞれが（n -1）を生成します。出力、および行い（N -1）再帰呼び出し、そうN（N -1）引数N -2と呼び出しがあります。ように、合計があるので、1 + N + N（N -1）+ N（N -1）（N -2）+ ... + n！コール。 Σ 私は≤ NNのように書くことができ

！/ I！または（Σ 私≤ N 1/I！）のn！または（e-1）、約1.71828 n！

出典

2017-03-18 18:09:46 rici

あなたの明確な説明をありがとう。しかし、なぜこのアルゴリズムが現れているのか分かりますか？このアルゴリズムは、すべての可能な順列を見つけるための他の方法よりも優れていますか？それとも、探索する別の新しい方法ですか？ありがとうございました。 –

@ USER1223_T：これはウィキペディアのページで説明されていると思います。（「アルゴリズムは動きを最小限に抑える」）私はそれを考えていた人がちょうどクールだと思ったと思う。それは50年以上前のことだったので、答えが出るかどうかは分かりません。私は、それが価値があるためのクールなアルゴリズムだと思う。 – rici

ヒープのアルゴリズムとヒープソートのアルゴリズムまたはヒープのデータ構造が混乱していると思います。後の2つはソートのためにO（NlogN）の複雑さがあります。

あなたが言及したアルゴリズムはすべての順列を生成するためのもので、N！すべてのN要素配列の順列では、複雑さはO（N！）です。

出典

2017-03-18 18:06:27 lazyc97

ご覧いただきありがとうございます。しかし、時間の複雑さが依然としてO（N！）なので、なぜそれらはすべての順列を見つけるためにこのアルゴリズムを開発するのだろうか？このアルゴリズムは、他のもの（他のすべての順列を見つけるための通常の方法）と比べて効率的ですか？ –

ヒープのアルゴリズム時間の複雑度

答えて

関連する問題