アルゴリズムの最悪の複雑さをどのように判断できるか教えてください。私は、Dがサイズnの入力のセットである場合、式W(n)= max {t(I)| Iの要素)を使用する必要があることを知っています。各要素Iに対して実行された操作の数を計算し、その最大値を取るか?これを達成するための簡単な方法は何ですか?アルゴリズムの最悪の複雑さを判断する
答えて
式から始めると、それは少し後ろ向きに考えられます。あなたが本当に気にしているのは、スケーラビリティです。入力のサイズを大きくすると、それは何をするのでしょうか。
たとえば、ループがある場合は、O(n)回の複雑さのアルゴリズムがあります。しかし、別のループ内にループがある場合は、任意のサイズnの入力に対してn^2を行う必要があるため、O(n^2)になります。
最悪の場合を話しているときは、通常、非決定論的なアルゴリズムについて言及しています。ここでは、ループが早期に停止する可能性があります。あなたがこれに対してしたいことは、最悪の場合を想定し、ループができるだけ遅く停止するように見せかけることです。だから我々が持っている場合は、(i = 0をint型;私< N;私は++)のため
{ のために(int型J = 0; jの< N; J ++){ (RAND()> 0.5)場合にj = n; }}
我々は最悪の場合はO(N^2)であることを言うでしょう。ミドルループが早期に破綻する可能性が高いことはわかっていますが、最悪の可能性を探しています。
この方程式は、アルゴリズムよりも定義のほうが多いです。
問題のアルゴリズムは入力のサイズ以外のものを気にしていますか?そうでなければ、W(n)を計算することは「容易」である。
もしそうであれば、病理学的入力を試してみてください。たとえば、クイックソートでは、ソートされた入力が病理学的なものであることはかなり明らかであり、O(n^2)ステップが必要であることを数えることができます。
:その時点で、あなたはどちらか
- は、あなたの入力が上位1位のいずれかの入力
例の実行時にバインドマッチング展示
「最大限」病的であると主張することができます クイックソートの各パスは、ピボットを正しい場所に置き、2つの部分で再帰します。 (ハンドウェイアラート)最悪の場合は、ピボットの片側に残りのアレイを配置します。ソートされた入力がこれを達成します。
#2の例:
クイックソートの各パスは適切な場所にピボットを置くので、O(N)以下ではありません通過します。各パスは、O(n)回の作業を必要としません。このように、入力はクイックソートにO(n^2)以上かかることはありません。
この場合、#2のほうがはるかに簡単です。
- 1. アルゴリズムの複雑さを判断する
- 2. アルゴリズムの最悪の複雑さ
- 3. 最悪の複雑さが入力サイズに反比例するアルゴリズム?
- 4. アルゴリズムの複雑さ
- 5. 複雑さのレベルを判断するためにSQLを解析する
- 6. アルゴリズムの複雑さ - エクササイズ
- 7. fooアルゴリズムの複雑さ
- 8. Dijkstraのアルゴリズム - 複雑さ
- 9. クイックソート最悪の場合の時間の複雑さ?
- 10. 非単調な最悪ケースの複雑さの例
- 11. この関数のアルゴリズムの複雑さ
- 12. 次のアルゴリズムの複雑さは?
- 13. f(n)コストでのアルゴリズムの複雑さ
- 14. リンクリストのアルゴリズム複雑さの分析
- 15. 関数の複雑さとアルゴリズム
- 16. アルゴリズムの時間複雑
- 17. n logn最悪の複雑さを持つクイックソートを実行できますか?
- 18. 時間の複雑さのためのアルゴリズムを分析する
- 19. 単語の複雑さを推定するアルゴリズム
- 20. 複雑なポリゴンを分解するアルゴリズム
- 21. 単語が英語かどうかを判断するアルゴリズム?
- 22. アルゴリズムのBig O/Timeの複雑さを見つける方法
- 23. デジタルオーディオデータがクリッピングされているかどうかを判断するアルゴリズム?
- 24. O(fib n)複雑アルゴリズム?
- 25. アルゴリズムの複雑さにおけるメモリ使用の影響
- 26. アルゴリズムのBigO時間の複雑度
- 27. プログラムはアルゴリズムの複雑さを計算できますか?
- 28. ユークリッドのGCD空間複雑度アルゴリズム
- 29. 再帰アルゴリズムの空間複雑度
- 30. 分割アルゴリズム - 時間の複雑度
非決定論についてはちょっと注意してください。早期に終了するループは非決定論的ではありません...決定論とは、プログラムが何をするかを明確に知ることができ、それが何をするかを決定できないことを指します。確率的またはランダム化されたアルゴリズムは、何が起こるのかわからないアルゴリズムのステップがあるため(乱数については言及していませんが、ランダム化されたアルゴリズム)、非決定的になります。 http://en.wikipedia.org/wiki/Non-deterministic_algorithm – Kekoa
明確ではなく、非決定論とランダム性の間に密接な関係があります。 Turin Machinesではランダム化されたアルゴリズムは乱数の(無限の)テープにアクセスできると考えています。ランダムなテープ(ランダムなシード)に何があるかを修正すれば、残りの部分は確定的です。しかしながら、非決定論的チューリング機械は、固定入力を与えられたある状態からいくつかの状態に移動することができる。 –