1

時間計算量について話すとき、通常、入力としてnを使用しますが、これは実際の入力サイズの正確な尺度ではありません。入力（ s ）に特定のサイズを使用する場合、アルゴリズムが同じ複雑度クラスのままであることを示すのに問題があります。

たとえば、単純なシーケンシャル検索アルゴリズムを考えてみましょう。最悪の場合、W（n）時間がかかります。特定の入力サイズ（2進数）を適用する場合、順序はW（lg L）になります。ここで、Lは最大の整数です。

シーケンシャル検索または任意のアルゴリズムが同じ複雑度クラス（この場合は線形時間）のままであることをどのように示すことができますか？ ある種の代用が必要なことは理解していますが、どうやって結論を出すのか迷っています。

編集

探していたものが見つかったと思いますが、よくわかりません。

最悪の場合の時間計算量をW（s）として定義する場合、入力サイズsのアルゴリズムによって実行される最大ステップ数、次に入力サイズの定義により、s = lg n、ここでnは入力です。次に、n = 2 ^ sであり、時間計算量はW（2 ^ s）であり、指数関数的複雑であるという結論に至ります。したがって、バイナリエンコーディングを使用したアルゴリズムのパフォーマンスは指数関数的であり、大きさの点で線形ではありません。

4

3 に答える 3

4

時間の複雑さについて話すときは、通常 n を入力として使用しますが、これは実際の入力サイズの正確な尺度ではありません。入力に特定のサイズを使用すると、アルゴリズムが同じ複雑さのクラスにとどまることを示すのに苦労しています。

たとえば、単純な順次検索アルゴリズムを考えてみましょう。最悪の場合、W(n) 時間かかります。特定の入力サイズ (基数 2) を適用する場合、順序は W(lg L) である必要があります。ここで、L は最大の整数です。

Lは、最大の整数を表す変数です。 nは、入力のサイズを表す変数です。 Lはnと同じように特定の値ではありません。

特定の値を適用すると、もはや複雑なクラスについて話しているのではなく、そのクラスのインスタンスについて話しているのです。

500 個の整数のリストを検索しているとしましょう。つまり、n = 500

Sequential Search の最悪の複雑度クラスはO(n)です

複雑さはn

最悪の場合の複雑さの特定のインスタンスは 500 です

編集：

値は、各値をエンコードするために必要なビット数が均一になります。入力が 32 ビット整数のリストの場合、c = 32 (整数あたりのビット数) です。複雑さは 32*n => O(n) になります。

L に関して、L が最大値であり、lg L が L をエンコードするために必要なビット数である場合、lg L は定数 c です。ビット単位での複雑さは O(n) = c*n です。ここで、c = lg L は一定の特定の入力サイズです。

于 2011-05-18T15:12:44.100 に答える
1

Lucia Mouraが述べているように、「単一符号化を除いて、自然数の他のすべての符号化は、多項式に関連する長さを持っています」

これがソースです。19ページをご覧ください。

于 2011-05-18T15:50:20.180 に答える
1

私が知っていることは、Sequential Search によって実行されるステップの最大数は、明らかに cn^2 + nlg L であるということです。cn^2 は、ループをインクリメントして分岐を行うためのステップ数です。

それはまったく真実ではありません。シーケンシャル検索で実行されるステップの最大数は c*n になります。ここで、n はリスト内のアイテムの数で、c は何らかの定数です。それは最悪のケースです。n^2成分や対数成分はありません。

たとえば、単純な順次検索は次のようになります。

for (int i = 0; i < NumItems; ++i)
{
    if (Items[i] == query)
        return i;
}
return -1;

NumItems/2そのアルゴリズムでは、各アイテムを検索すると、検索の半分で必要な反復回数は 未満になり、検索の半分で必要なNumItems/2反復回数は 1 回以上になります。検索する項目がリストにない場合は、それNumItemsを判断するために反復が必要になります。最悪の場合の実行時間はNumItems反復です。平均的なケースはNumItems/2反復です。

実行される操作の実際の回数は、ある定数Cに反復回数を掛けたものです。平均してC*NumItems/2です。

于 2011-05-18T15:52:27.543 に答える