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

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

Подсказки/Советы/Советы широко открыты!

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


algorithm data-structures trie
person bragboy    schedule 27.02.2010    source источник
comment
Вам не хватает важного члена в вашей структуре TRIE?   -  person kennytm    schedule 27.02.2010
comment
@Kenny: Да, извините, у него должен быть персонаж.   -  person bragboy    schedule 27.02.2010

Ответы (2)


arrow_upward
1
arrow_downward

Если вы действительно хотите использовать trie, то 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 — количество символов в вашем документе.

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

person IVlad    schedule 27.02.2010
comment
Либо вы неправильно поняли мой вопрос, либо я не объяснил. Это не только подсчет слов. Его подсчет уникальных слов. После построения структуры данных я должен иметь возможность указать количество слов для любого вводимого слова, и я решительно поддерживаю идею использования здесь TRIE. Извините, если мой вопрос был расплывчатым. Позвольте мне исправить это - person bragboy; 27.02.2010
comment
Извини, я думал, тебе нужно только считать слова. В таком случае игнорируйте вторую часть моего поста. Попытка — хороший колл. Моя первая часть все еще остается в силе - вы можете построить свою тройку в O (C) (при условии, что вам НЕ НУЖНО использовать функцию getNextWord(), если вы это сделаете, ваше решение в порядке) и ответить на любой запрос для слова длины k за О(к). - person IVlad; 27.02.2010
comment
Спасибо за понимание. Согласно вашему решению, мы можем найти его за время O(C), но это равно O(Nk), верно? И причина, по которой я должен использовать getNextWord(), заключается в том, что это единственный общедоступный метод, доступный мне. У меня нет указателя на документ. Наверное, в следующий раз я должен быть яснее, когда задаю вопросы :) - person bragboy; 27.02.2010
comment
Теоретически O(C) и O(Nk) — одно и то же, но на практике мое решение O(C) будет быстрее. Если у вас есть процедура, которая вставляет слово, полученное с помощью getNextWord(), в ваше дерево, то сначала getNextWord() должна будет получить слово, которое равно O(k), а затем ваша процедура вставки займет O(k), чтобы вставить его. в три. Таким образом, в основном вы будете проходить каждое слово и, следовательно, каждый символ дважды, в то время как мое решение будет проверять каждый символ только один раз. В любом случае, то, что я сказал, неприменимо, если вы должны использовать getNextWord(), поэтому время работы вашего алгоритма равно O(Nk) или O(C). - person IVlad; 27.02.2010
comment
При заданных ограничениях постановки задачи ваше решение является оптимальным как в теории, так и на практике. O(Nk) == O(C), потому что Nk в основном C (количество слов N, средняя длина слова k, умножьте их, и вы получите среднее количество символов, то есть C). Я использовал O(C), чтобы подчеркнуть тот факт, что алгоритм отличается и в целом немного лучше. - person IVlad; 27.02.2010
comment
Я смущен. Как второй код помогает генерировать количество слов (а не общее количество слов)? - person kennytm; 28.02.2010
comment
@KennyTM: это не так, я сначала неправильно понял вопрос. Актуален только первый код, вторую часть я оставил на всякий случай, может кому пригодится. - person IVlad; 28.02.2010

arrow_upward
2
arrow_downward

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

person kennytm    schedule 27.02.2010