Verwirrung in der Reihenfolge der Datenstruktur zu finden,

Question

Heute besuchte ich einen schriftlichen Test von einem Unternehmen durchgeführt. Der Gesamttest wurde auf Datenstrukturen fokussiert. Ich habe ein Problem, das ich dachte, ich gelöst. Aber ich hatte eine harte Zeit, um die Big O-Funktion für die Datenstruktur bei der Berechnung. Ich werde die Frage geben, und die Antwort, die ich kam mit.

  

Bei einem Dokument, das Sie brauchen, zu speichern und die Worte in dem Dokument und soll die Zählung zurückkehren kann, wenn ein Wort eingegeben wird. Sie sind mit char* GetNextWord() zur Verfügung gestellt.

     

  
1. Welche Datenstruktur werden Sie
wählen   
2. Geben Sie den Algorithmus
  
3. Was die Reihenfolge des Algorithmus
wird   

Frage 1, schrieb ich, dass ich gehe für Trie-Datenstruktur. Zu Frage 2, gab ich einen kurzen Algorithmus. Ich schrieb ich würde die Trie-Datenstruktur wie folgt konstruieren.

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

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

Ich habe Methoden constructTrie(), die eine addToTrie() für jedes Wort tun.

Ich schrieb den Auftrag von addToTrie() wäre O ( k ) wobei k ist die Länge. Und die Reihenfolge der constructTrie() wäre N * O ( k ) wobei N würde die Anzahl der Wörter sein.

Jetzt ist meine Frage: Ob die Aufträge die ich erwähnt habe, ist richtig oder nicht? Wenn nicht, wie in der Zukunft Probleme wie diese attackieren (bei einem DS den Auftrag zu finden). Ich habe wirklich verwirrt nach O mit ( k ). Es macht mich annehmen O (1).

Hinweise / Tips / Advise sind weit geöffnet !!

Bearbeiten :. Die Frage eindeutig Korrigierte zu erwähnen, dass die Wortanzahl für alle eindeutigen Wörter gespeichert werden sollen

Answer 1

Wenn Sie wirklich ein Trie verwenden wollen, dann würde addToTrie() in der Tat sein, O (k) wobei k die Länge des Wortes Sie hinzufügen. constructTrie() würde O (Nk) , wobei N die Anzahl der Wörter ist, wenn Sie gerade Anruf addToTrie() für jedes Wort. Allerdings müssen Sie nicht die addToTrie() Funktion für jedes Wort nennen. Wenn Sie fertig sind, ein Wort hinzufügen, stellt gerade einen Trie-Zeiger auf die Wurzel des Trie, dann den Zeiger bewegen, wie Sie über Ihr aktuelles Wort bewegen, das Hinzufügen der Zeichen, wie Sie gehen zusammen. Pseudo-Code:

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;

Dies wird Ihnen O (C) Zeit für den Aufbau des Trie ausgeführt wird, wobei C ist die Anzahl der Zeichen in Ihrem Dokument.

Nun stellt sich die Frage: Warum brauchen Sie das trie überhaupt? Offensichtlich rechnet man einen Ausweg zu erkennen, wenn ein Wort zu Ende ist, also warum müssen Sie Ihre Worte zu einem Trie hinzufügen? Es ist übertrieben. Die einzige Datenstruktur brauchen, ist ein paar Variablen: eine Spur des aktuellen Zeichen zu halten, eine Spur des vorherigen Zeichens zu halten und man die Worte zu zählen. Dies ist leicht getan in O (C) wie folgt aus:

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;

Ich denke, es macht keinen Sinn, einen Trie für dieses Problem zu verwenden, ist es nur ist komplizieren Dinge. Ich denke, wenn sie Ihr Wissen über versucht testen, wollte sie würden Sie ein Problem gegeben haben, wo ein Trie mehr Sinn gemacht.

Auch wenn sie gaben Sie eine getNextWord() Funktion (Hattest du es zu benutzen? Weil Sie ohne es besser machen kann), ich vermute, es „\ 0“ oder etwas zurückgibt, wenn es keine Worte mehr sind? Also, warum nicht Sie nennen es einfach, bis es „\ 0“ zurückkehrt und die Worte so zählen? So oder so, ist ein Trie nicht wirklich Sinn hier machen.

Answer 2

Der Vergleich zweier generische Strings nehmen Θ (k) (k = min Strlen), und die Anzahl der Wörter ist N, die Sie schauen durch, also Ω (Nk) sollte die effizienteste Komplexität, die Sie bekommen können.