1

試験の準備をしていますが、実行時間分析で少し問題があります。以下の2つの方法がありますが、実行時の分析で混乱しています。

 public boolean findDuplicates(String [] arr) {
    Hashtable<String,String> h = new Hashtable<String,String>();
    for (int i = 0; i < arr.length; i++) {
         if (h.get(arr[i]) == null)
              h.put(arr[i], arr[i]);
         else
              return true;
         }
    return false;
    }

ハッシュ関数が任意のキーで O(1) しかとらないと仮定すると、最悪の場合、配列全体を実行するため、実行時間は単純に O(n) になりますか? 各ハッシュ関数の評価に一定の時間がかかる場合、これを正しい方向に考えていますか?

私が抱えている他の問題はもっと複雑に思えますが、これにどのようにアプローチすればよいか正確にはわかりません。これらが不法行為者であると仮定します。

public boolean makeTranslation(List<Integer> lst1, List<Integer> lst2) {
//both lst1 and lst2 are same size and size is positive
     int shift = lst1.get(0) - lst2.get(0);
     for (int i = 1; i < lst1.size(); i++)
          if ( (lst1.get(i) - lst2.get(i)) != shift)
               return false;
     return true;
}

この場合、特定のインデックス値を取得しているだけなので、取得操作は定数であると想定されます。しかし、for ループでは、それをシフトと比較し、すべての要素を反復しています。これは実行時間にどのくらい正確に変換されますか?

私はこのコースで何よりも実行時間分析を理解するのに最も苦労しており、私の最終は来週であるため、有益な説明をいただければ幸いです。

4

4 に答える 4

1

簡単な答え: どちらの方法も時間の複雑さはO(n)です。

getハッシュの場合、とput操作の両方に一定の時間がかかることは明らかです。

リストの場合、ArrayList実装を使用する場合 (そしてその可能性が高い)、getメソッドにも一定の時間がかかります。これはArrayList、JavaListの が配列に基づく であるためです。

ArrayList.get(index)標準 Java ライブラリのコード:

public E get(int index) {
    RangeCheck(index);
    return (E) elementData[index];
}

RangeCheckおそらく一定時間である2つの比較を行いました。から値を返すことarrayは明らかに一定の時間です。したがって、getメソッドにArrayListは一定の時間がかかります。

OPで言及されているあなたの特定の懸念について：

しかし、for ループでは、それをシフトと比較し、すべての要素を反復しています。これは実行時間にどのくらい正確に変換されますか?

lst1.get(i)一定の時間がかかります。lst2.get(i)一定の時間がかかります。したがって、lst1.get(i) - lst2.get(i)一定の時間がかかります。についても同様です(lst1.get(i) - lst2.get(i)) != shift。アイデアは、一定数の一定時間操作の合計が一定時間であるということです。ループはn回まで繰り返されるため、合計時間はO(Cn)O(n) になります。ここで、C は定数です。

そして...最後の直前に大きなO表記を簡単に確認するのは決して悪いことではありません:)

于 2012-12-05T02:52:24.367 に答える
0

一般に、O（）は、各操作のコストが一定であると仮定すると、一般に操作の数であるアルゴリズムの複雑さを表します。たとえば、O（1000n）は、各操作がO（n）を記述するのと同様です。コストは1000で、n回の操作があります。

したがって、getとputがすべての値に対して一定（ライブラリの実装に依存）であると仮定すると、両方の時間はO（n）になります。詳細については、http： //en.wikipedia.org/wiki/Big_O_notationを参照してください。

于 2012-12-05T01:29:18.810 に答える
0

Big-O 表記法は、定数因子と低次項を省略しているため、あまり正確ではありません。したがって、2 つの定数操作を n 回行ったとしても、それは O(n) になります。実際には (1+1)n=2n となりますが、オルド表記では (10000n であっても) 切り捨てます。したがって、これらの両方の場合で、実行時間は O(n) になります。

実際には、最悪の場合の各ループと各操作のコストを入力することをお勧めします。最も内側のネストされたレベルから開始し、外側に向かって乗算します (各レベルの最大コストのみ)。

例えば：

for (int i = 0; i<n; i++) { //n times
    //log n operation
    for (int i = 0; i<n; i++) { //n times
        //constant operation
    }
}

ここで、n>log(n) として n*(log(n)+n*1)=O(n*n) となります。

于 2012-12-05T01:23:02.227 に答える
0

エコーする価値はありますが、これらの操作はどちらもO(n)です (#2 の場合、これが最悪のケースです)。注意すべき重要なことは、各反復で実行される重要な操作の数です。

最初のスニペットでHashtableは、アクセス時間がループ内で最大の操作になるわけではないため、これは少し厄介です。また、それHashtableはちょうどnew'dだったので、常にn 個の要素を挿入することになります。

2 番目のスニペットでは、早期に終了する可能性があります。次の要素の差が でない場合はshift、すぐに戻っfalseてから、1 回の操作で済みます。最悪の場合、すべてのnを通過して戻ることになります。

于 2012-12-05T03:23:28.530 に答える