数据结构中寻找顺序的困惑

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)。

提示/建议非常欢迎！ 编辑：更正问题，明确说明所有唯一单词都应存储其单词计数。

- bragboy

---

你的 TRIE 结构体中是否缺少了一个重要成员？ - kennytm

@Kenny：是的，抱歉应该有一个字符。 - bragboy

Answer 1

比较两个通用字符串需要 Θ(k) 的时间（其中 k = 最小字符串长度），并且你需要查找的单词数量为 N，因此 Ω(Nk) 应该是您可以获得的最有效复杂度。

- kennytm

Answer 2

如果你真的想使用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;

这将为您构建Trie树提供O(C)的运行时间，其中C是文档中字符的数量。

现在，这引出了一个问题：为什么你需要Trie树呢？显然，您已经找到了一种检测单词结束的方法，那么为什么必须将单词添加到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;

我认为在这个问题中使用trie树没有意义，只会让事情变得更加复杂。如果他们想要测试你对trie树的了解，他们会给你一个更适合使用trie树的问题。

即使他们给了你一个getNextWord()函数（你必须使用它吗？因为你可以不用它做得更好），我猜当没有更多单词时它会返回"\0"或其他东西？那么为什么不能一直调用它直到它返回"\0"并像那样计算单词数呢？无论如何，在这里使用trie树都没有太大意义。

- IVlad

---

要么你没有理解我的问题，要么我没有表达清楚。这不仅仅是计算单词数量，而是计算唯一单词的数量。在构建数据结构之后，我应该能够为任何输入的单词提供单词计数，并且我强烈支持在这里使用TRIE的想法。 如果我的问题含糊不清，我向你道歉。让我来更正一下。 - bragboy

感谢您的理解。根据您的解决方案，我们能够在O(C)时间内找到它，但这等于O(Nk)对吧？而我必须使用getNextWord()的原因是，那是唯一可用于我的公共方法。我没有指向文档的指针。下次发帖时可能应该更清楚明确 :) - bragboy

在理论上，O（C）和O（Nk）是相同的事物，但在实践中，我的O（C）解决方案会更快。如果您有一个将getNextWord（）检索到的单词插入到trie中的过程，则首先getNextWord（）将需要获取该单词，这是O（k），然后您的插入过程将花费O（k）将其插入trie中。因此，基本上您将遍历每个单词，因此每个字符都要遍历两次，而我的解决方案只需检查每个字符一次。无论如何，如果您必须使用getNextWord（），则算法的运行时间为O（Nk）或O（C）。 - IVlad

在问题陈述的给定限制下，您的解决方案在理论和实践中都是最优的。O(Nk) == O(C)，因为Nk基本上就是C（N个单词，k个平均单词长度，将它们相乘并得到平均字符数，即C）。我使用O(C)来强调算法不同且一般而言更好的事实。 - IVlad

我有点困惑。第二段代码如何帮助生成单词的计数（而不是总单词数）？ - kennytm