algorithm - 寻找数据结构顺序的困惑

Question

今天参加了一家公司的笔试。整体测试侧重于数据结构。我遇到了一个我认为已经解决的问题。但是我在计算数据结构的 Big O 函数时遇到了困难。我将提供问题和我想出的答案。

Given a document you need to store and the words in the document and should be able to return the count when any word is entered. You are provided with char* GetNextWord().

1. What Data structure will you choose
2. Give the Algorithm
3. What will be the order of your algorithm

对于问题 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)。

提示/提示/建议是敞开的!!

编辑:更正了明确提到应为所有唯一单词存储字数的问题。

Answer 1

比较两个通用字符串需要 Θ(k) (k = min strlen)，并且您必须查看的单词数为 N，因此 Ω(Nk) 应该是您可以获得的最有效的复杂度。