2

以下のように、シェルソートアルゴリズムの分析について言及されているアルゴリズムに関する本を読んでいます。

Shell のインクリメントを使用した、Shellsort の最悪の場合の実行時間は、Theta(n 平方) です。

この証明には、最悪の場合の実行時間の上限を示すだけでなく、実行に Omeaga(n 平方) 時間として実際に下限を取る何らかの入力が存在することを示す必要があります。悪いケースを構築することにより、最初に下限を証明します。

上記の私の質問は次のとおりです。

  1. なぜ著者は下限をチェックするために悪いケースに言及しているのですか? 下限を取得するように教えましたが、最善のケースを採用する必要があります。上記を明確にするようお願いします。

ありがとう！

4

3 に答える 3

0

シータは境界制約です（上部と下部の両方）。アルゴリズムの実行時間がTheta（f（n））であることを示すには、次の2つのことを確立する必要があります。

1）最悪の場合、アルゴリズムはすべての場合で時間O（f（n））で実行されます[最悪の場合の複雑さ]

2）アルゴリズムには時間がかかる必要がありますOmega（f（n））[最悪のシナリオに当てはまる実際の例があります]

アルゴリズムの特に悪いケースを見つけることによって、2番目の部分を確立します。

于 2011-09-09T12:57:06.937 に答える
0

何かがTheta(f(n))であることを示すには、上限と下限の両方を示す必要があります。これが、テキストが行っていることです。

「最悪の場合の時間は Theta(n 平方) である」という主張には、最悪の場合の時間の上限と下限の両方を示す必要があります。

同様に、平均ケース時間が Theta(f(n))であるというステートメントは、平均ケース時間に 2 つの境界を必要とします。

等々。

@ Patrick87が簡潔に述べているように：

境界はケースに直交します。

于 2011-09-09T12:45:02.070 に答える
0

彼が上限と下限の両方を検討している理由は、最悪の場合の時間をTheta(Θ) 表記を使用して表現したいからです。

シータ表記では、上限と下限の両方を確立する必要があります。

于 2011-09-09T12:44:07.857 に答える