1

JavaScript 表記の使用:

A = {color:'red',size:8,type:'circle'};

L = [{color:'gray',size:15,type:'square'},
     {color:'pink',size:4,type:'triangle'},
     {color:'red',size:8,type:'circle'},
     {color:'red',size:12,type:'circle'},
     {color:'blue',size:10,type:'rectangle'}];

L[2] は A と同一であるため、この場合の答えは 2 になります。それぞれの可能性をテストすることで、O(n) で答えを見つけることができます。その答えをより速く見つけることを可能にする表現/アルゴリズムは何ですか?

4

4 に答える 4

1

HashMap を作成し、すべてのオブジェクトを HashMap に配置します。また、オブジェクト内のデータの関数であるハッシュ関数を定義する必要があります (Java で Object.hashcode() をオーバーライドするようなもの)。

与えられた配列 L が [B, C, D] であると仮定します。ここで、B、C、および D はオブジェクトです。その場合、HashMap は {B=>1, C=>2, D=>3} になります。ここで、D が A のコピーであるとします。したがって、このマップで A を検索して、答えを取得します。また、Eric P がコメントで示唆しているように、配列 L の変更に関してハッシュマップを更新し続ける必要があります。これは、配列 L のすべての操作に対して O(1) でも実行できます。

HashMap でオブジェクトをルックアップするコストは O(1) です。したがって、O(1) の複雑さを実現できます。

于 2012-09-02T19:00:52.800 に答える
0

目標はAのクローンであるすべてのオブジェクトを見つけることであるため、すべてのオブジェクトを少なくとも1回テストして、それがAのクローンであるかどうかを判断する必要があります。したがって、テストの最小数はNです。リストを1回通過し、各オブジェクトをテストします。 N回のテストを実行するため、この方法はテストの最小数であるため、最適な方法です。

于 2012-09-02T19:14:45.397 に答える
0

O(n)あなたの前提条件よりも速くそれを行うことは不可能だと思います。O(logn)二分探索を使用して要素を見つけることは可能ですが、次のようになります。

  • A）比較する1つの変数を持つ要素が必要です
  • B）その変数でソートされたリスト

いくつかの技術 (順序付け、スキップ リストなど) を使用すると、N 回の反復よりも速く答えを見つけることができますが、最悪の場合は次のようになります。O(n)

于 2012-09-02T18:58:28.110 に答える
-1

まず、リストではなく配列について話していると思います。「リスト」という単語は、O(n) インデックスの複雑さを持つ特定のタイプのデータ構造用に予約されているため、その中の検索は少なくとも線形です。

ソートされていない配列の場合、唯一のアルゴリズムは線形時間によるフル スキャンです。ただし、配列がソートされている場合は、バイナリ検索または補間検索を使用してより良い時間を取得できます。

並べ替えられた配列の問題は、挿入時間が線形であることです。ダメ。したがって、セットを頻繁に更新する必要があり、更新時間と検索時間の両方が重要な場合は、最適化されたコンテナーを検索する必要があります。これは、c++ と haskell で呼び出されますSet(それぞれヘッダーのsetテンプレートとパッケージのモジュール)。JSに何かあるかどうかはわかりません。setData.Setcontainers

于 2012-09-02T21:14:13.733 に答える