4

今日、会社が実施する筆記試験を受けました。全体的なテストは、データ構造に焦点を当てていました。解決したと思っていた問題が発生しました。しかし、データ構造の Big O 関数を計算するのに苦労しました。私が思いついた質問と答えを提供します。

保存する必要があるドキュメントとドキュメント内の単語を指定すると、単語が入力されたときにカウントを返すことができるはずです。が提供されchar* GetNextWord()ます。

  1. どのデータ構造を選択しますか
  2. アルゴリズムを与える
  3. アルゴリズムの順序はどうなりますか

質問 1 では、TRIE データ構造に行きますと書きました。質問 2 では、簡単なアルゴリズムを示しました。私は次のようにTRIEデータ構造を構築すると書きました。

struct TRIE{
 boolean isWord;
 int count;
 Node* myList;
}

struct Node{
 char* character;
 Node *next;
 TRIE *child;
}

各単語に対してconstructTrie()実行するメソッドがあります。addToTrie()

addToTrie()の順序はO( k )と書きました。ここで、 kは長さです。の順序はconstructTrie()N * O( k ) で、Nは単語数です。

私の質問はこれです: 私が言及した注文が正しいかどうか? そうでない場合は、将来このような問題にどのように対処するか (ds が注文を見つけた場合)。O( k )を使用した後、私は本当に混乱しました。O(1)だと思い込んでしまいます。

ヒント/ヒント/アドバイスは大公開!!

編集：すべての一意の単語の単語数を保存する必要があることを明確に述べている質問を修正しました。

4

2 に答える 2

2

2 つの一般的な文字列を比較するには Θ(k) (k = min strlen) が必要であり、単語の数は N であり、調べなければならないため、Ω(Nk) は取得できる最も効率的な複雑さである必要があります。

于 2010-02-27T07:47:16.947 に答える
1

本当にトライを使用したい場合は、addToTrie()実際にはO(k)になります。ここで、k は追加する単語の長さです。すべての単語を呼び出すだけの場合、Nは単語の数であるO(Nk)constructTrie()を取ります。ただし、すべての単語に対して関数を呼び出す必要はありません。単語の追加が完了したら、トライ ポインターをトライのルートにリセットし、現在の単語の上を移動しながらポインターを移動し、文字を追加します。擬似コード:addToTrie()addToTrie()

trieNode *curr = trieRoot;
for each character c in document
  if it's a word terminator (space etc)
    add a character at curr signaling the end of the current word ('\0' maybe);
    curr = trieRoot;
  else if character is not a separator
    add character c at curr->next->character[c];
    curr = curr->next;

これにより、トライを構築するためのO(C)実行時間が得られます。ここで、 Cはドキュメント内の文字数です。

さて、ここで疑問が生じます: なぜトライが必要なのですか? 単語がいつ終了したかを検出する方法を明らかに理解したのに、なぜ単語をトライに追加する必要があるのでしょうか? それはやり過ぎです。必要な唯一のデータ構造は、いくつかの変数です。1 つは現在の文字を追跡する変数、1 つは前の文字を追跡する変数、もう 1 つは単語をカウントする変数です。これは、次のようにO(C)で簡単に実行できます。

char prev = '\0';
char curr;
int count = 0;

for each character curr
  if curr is a word separator and prev isn't 
    ++count;
  prev = curr;

この問題にトライを使うのは意味がないと思います。それは物事を複雑にするだけです。彼らがあなたのトライに関する知識をテストしたいのであれば、トライがより意味のある問題を出していただろうと思います。

彼らがあなたにgetNextWord()関数を与えたとしても（あなたはそれを使わなければなりませんでしたか？それがなくてもうまくいくので）、それ以上単語がないときに「\ 0」または何かを返すと思いますか？では、「\0」が返されるまで呼び出して、そのように単語を数えることができないのはなぜですか? いずれにせよ、トライはここではあまり意味がありません。

于 2010-02-27T08:51:20.777 に答える