Путаница в поиске порядка структуры данных

Question

Сегодня я присутствовал на письменном тесте, проводимом компанией. Общий тест был сфокусирован на структурах данных. У меня проблема, которую я решил решить. Но мне было нелегко вычислить функцию 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 будет количество слов.

Теперь мой вопрос такой: Являются ли упомянутые мной заказы правильными или нет? Если нет, то как атаковать подобные проблемы в будущем (учитывая, как найти порядок). Я действительно запутался после использования O ( k ). Это заставляет меня предположить O (1).

Советы / Советы / Советы широко открыты !!

Редактировать : исправлен вопрос, в котором четко указано, что количество слов должно храниться для всех уникальных слов.

Answer 1

Сравнивая две общие строки, возьмите & Theta; (k) (k = min strlen), и количество слов равно N, которое вам нужно просмотреть, поэтому & Omega; (Nk) должна быть наиболее эффективной из возможных сложностей.

Answer 2

Если вы действительно хотите использовать три, тогда addToTrie() будет действительно O (k) , где k - длина добавляемого вами слова. constructTrie() будет принимать O (Nk) , где N - количество слов, если вы просто наберете addToTrie() для каждого слова. Однако вам не нужно вызывать функцию addToTrie() для каждого слова. Как только вы закончите добавлять слово, просто сбросьте указатель trie на корень trie, затем переместите указатель, когда вы перемещаетесь по текущему слову, добавляя символы по мере продвижения. Псевдокод:

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 - количество символов в вашем документе.

Теперь возникает вопрос: зачем вам вообще нужен три? Очевидно, вы нашли способ определить, когда слово закончилось, так почему вы должны добавить свои слова в три? Это излишне. Единственная необходимая структура данных - это несколько переменных: одна для отслеживания текущего символа, одна для отслеживания предыдущего символа и одна для подсчета слов. Это легко сделать в 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", и не посчитать такие слова? В любом случае, здесь три не имеет смысла.