1

私はアルゴリズムにかなり慣れていないので、いくつか質問があります。O（n ^ 2）でデータをソートするソートアルゴリズムがあり、実行時間の複雑さがあるとしましょう。これは、たとえば選択ソートである可能性があります。ここで、選択ソートを使用する代わりに、実行時間を O(n) に短縮する HashTable を使用するとします。

  • 追加のスペースの複雑さは、実行時間分析に影響しますか?
  • 答えを述べるとき、これら 2 つの関係をどのように定義すればよいでしょうか?
  • それとも、それらはまったく異なるものですか？

どんな助けでも大歓迎です。

4

2 に答える 2

0

分析がアルゴリズムの時間の複雑さに焦点を当てている場合は、各操作のコストにのみ注目する必要があります。

分析がアルゴリズムの時間と空間の複雑さに焦点を当てている場合は、各操作の時間とデータ構造の空間コストに焦点を当てる必要があります。

時間と空間は異なる資源であるため、時間と空間の分析は別々に行う必要があります。

そうは言っても、時空間のトレードオフという重要な概念があります。 つまり、特定のアルゴリズムの取引時間をスペースで変更でき、その逆も可能です。

たとえば、複雑でスペースを消費するが高速なデータ構造を導入することで、時間の複雑さを軽減できます。これは時間 -> スペースのトレードオフの例です。これは、メモリ使用量の増加を犠牲にしてアルゴリズムを高速化するためです。

于 2012-08-04T18:02:59.497 に答える
0

理論的アルゴリズム理論の実行時間分析であれば、空間の複雑さは実行時間の複雑さに影響しません。時間計算量について話すときは、 無限のメモリを持つTuring Machine上のプログラムの時間計算量について話しているからです。

スペースと時間のトレードオフは、アプリケーションのみです。参照については、@Haile の投稿を参照してください。

于 2012-08-04T18:14:06.273 に答える