4

目標：

(1) テキスト ドキュメントを表す文字列と、(2) 返されるアイテムの数を提供する整数の 2 つのパラメーターを受け取る関数を作成します。最も頻繁に出現する単語が最初になるように、単語の頻度で並べ替えられた文字列のリストを返すように関数を実装します。最善の判断を行って、単語の区切り方を決定してください。ソリューションは O(n) 時間で実行する必要があります。ここで、n はドキュメント内の文字数です。

私の考えでは、最悪の場合、関数への入力はドキュメント内の単語の総数であり、単語を頻度でソートする問題が軽減される可能性があります。これにより、比較ソート法を使用した場合、時間の複雑さの下限は O (n log n) になると思いました。したがって、私の考えでは、最善のアプローチはカウントソートを実装することでした。これが私のコードです。

私の分析が正しいかどうか教えていただきたいのですが、コードに時間計算量についての私の考えを注釈として付けましたが、それは間違いなく間違っている可能性があります。このコードの実際の時間と空間の複雑さは? また、これが実際に良いアプローチであるかどうか、実際に使用される代替アプローチがあるかどうかも知りたいです。 

### n is number of characters in string, k is number of words ###
def word_frequencies(string, n)
  words = string.split(/\s/)  # O(n)
  max = 0
  min = Float::INFINITY
  frequencies = words.inject(Hash.new(0)) do |hash,word|  # O(k)
    occurrences = hash[word] += 1                     # O(1)
    max = occurrences if occurrences > max            # O(1)
    min = occurrences if occurrences < min            # O(1)
    hash;                                             # O(1)  
  end

  ### perform a counting sort ###
  sorted = Array.new(max + words.length)

  delta = 0

  frequencies.each do |word, frequency|   #O(k)
    p word + "--" + frequency.to_s
    index = frequency
    if sorted[index]
      sorted[index] = sorted[index].push(word)  # ??? I think O(1).
    else
      sorted[index] = [word]                    # O(1)
    end
  end

  return sorted.compact.flatten[-n..-1].reverse   
  ### Compact is O(k).  Flatten is O(k).  Reverse is O(k). So O(3k)
end

### Total --- O(n + 5k) = O(n).  Correct? 
### And the space complexity is O(n) for the hash + O(2k) for the sorted array.  
### So total O(n).


text = "hi hello hi my name is what what hi hello hi this is a test test test test hi hi hi what hello these are some words these these"

p word_frequencies(text, 4)
4

3 に答える 3

2

1つのアイデアは次のとおりです。

  1. 特定の単語の頻度を示すハッシュ マップを既に作成しています。
  2. 次に、このハッシュ マップを繰り返し処理し、逆の「ハッシュ セット」を作成します。これは、特定の頻度の単語のセットです。
  3. 最大頻度を見つけ、その頻度の単語のセットを出力します。
  4. それをデクリメントし、ハッシュ セット内の単語をチェックします。
  5. 必要な単語数までこれを続けます。

このアルゴリズムの次数は O(f) で、f は任意の単語の最大頻度です。任意の単語の最大頻度は、n が必要な文字数である場合、多くても n でなければなりません。

于 2013-11-12T09:15:40.050 に答える