O（N）Oまで（LOGN）

Question

から複雑さを変更する我々は、3つの整数 USERIDは含まratings呼ばLinkedListは、アイテムIDおよび（0から10までの例）実際の格付けの値を有する この方法は、実際の評価を返しますユーザーのプログラムがファイルとリターンからそれを読み込むこと-1は評価

BigOh（n）は方法がない場合はiとアイテムjの：

public int getRating(int i, int j){ 
    ratings.findFirst(); 
    while(!ratings.empty()){ 
     if(ratings.retrieve().getUserId() == i && ratings.retrieve().getItemId() == j) 
      return ratings.retrieve().getValue(); 
     else 
      ratings.findNext(); 
    } 
    return -1; 
} 

はどうすればこれを行うことができますBigOh（logn）で？
または、バイナリ検索ツリーを使用して解決できますか？

Answer 1

ハッシュを使用してO（1）にタスクを実行できます。ハッシュについて深く理解するには、articleをお読みください。

Javaを使用しているので、HashMapを使用して作業を完了できます。 hashing技法の最悪の場合の時間複雑度はO（log n）であるが、平均してO（1）であることに留意されたい。ハッシュテーブルと償却分析について知りたい方は、articleをご覧ください。

コード例：あなたが必要な属性を持つClassを作成し、以下のようにequalsとhashCodeメソッドを実装することができます。次のようにHashMapに続い格納値

class Rating { 

    public int user_id; // id of the user who rated 
    public int item_id; // id of the item being rated 

    public Rating(int user_id, int item_id) { 
     this.user_id = user_id; 
     this.item_id = item_id; 
    } 

    @Override 
    public boolean equals(Object o) { 
     if (o == this) { 
      return true; 
     } 
     if (!(o instanceof Rating)) { 
      return false; 
     } 
     Rating ratingObj = (Rating) o; 
     return ratingObj.user_id == user_id 
       && ratingObj.item_id == item_id; 
    } 

    @Override 
    public int hashCode() { 
     int result = 17; 
     result = 31 * result + user_id; 
     result = 31 * result + item_id; 
     return result; 
    } 
} 

を[Java collections - hashCode() and equals()を読む]：

public static void main(String[] args) { 
    HashMap<Rating, Integer> ratingMap = new HashMap<>(); 
    Rating rt = new Rating(1, 5); // user id = 1, item id = 5 
    ratingMap.put(rt, 3); 
    rt = new Rating(1, 2); // user id = 1, item id = 2 
    ratingMap.put(rt, 4); 
    rt = new Rating(1, 3); // user id = 1, item id = 3 
    ratingMap.put(rt, 5); 

    // now search in HashMap 
    System.out.println(ratingMap.get(new Rating(1, 3))); // prints 5 
} 

Answer 2

を提示したように、これはほとんど（ログn）Oで行うことはできませんでした。必要な要素が見つかるまで要素を探しています。最悪の場合、ループの終わりまで必要な要素が見つからないため、O（n）になります。

もちろん、ratingsが辞書であれば、ほとんどのO（1）：user idsをキーとして取得し、たとえば評価として値のリストを取得します。挿入は少し遅くなりますが、それほど多くはありません。

Answer 3

簡単な答えは、異なるデータ構造を使用することです。リンクされたリストは何の検索も行うことができません他各要素は実際の類似や順序なしでリンクされています（の場合はリストがソートされていても、種類のタイムドトラバーサル）。

使用できるデータ構造は、GuavaのTableです。このデータ構造を使用すると、中...

Table<Integer, Integer, Rating> ratings = HashBasedTable.create(); 
ratings.put(rating.getUserId(), rating.getItemId(), rating); 

に要素を追加に多くの作業を行う必要があるだろう...しかし、あなたはすぐに非常にを取得することができます - およそO（1）時間であるためHashBasedTableはLinkedHashSet<Integer, LinkedHashSet<Integer, Rating>>によってサポートされています。

ratings.get(i, j);