trie的复杂性

-3

如果必须至少读取输入字符串数组中的所有字符以逐个将字符串插入到trie中，如何使用trie？所以复杂度是O（size_of_array）。假设输入的字符串数组是{"hello",world","stack","overflow"}，并且我们想要搜索“stack”，那么我们将不得不遍历整个数组，以将键插入到trie中。所以复杂度是O（size_of_array）。我们可以做到这一点没有trie。trie的复杂性

来源

2015-06-27 Saurabh

特里特点是许多查询。

一个trie提供了一个相对便宜的插入每个字符串。
一个trie提供了一个相对便宜的字符串搜索。

这意味着，如果你有一个数组，你需要查询在一个字符串的存在只是一次 - 它可能不会有很大的帮助，从创建线索的单个查询是一种浪费。然而，如果你有一本字典，并且你将在数百万次的时间内查询它，那么搜索trie比重新搜索数组效率更高，这就是你从中受益的地方。

来源

2015-06-27 08:41:51 amit

@amit从我的经验来看，实际情况并非如此（这是一种非常慢的数据结构，用作字典）。尽管如此，它还是一个很好的自动完成程序，并具有其他一些（有限适用性）的用途。 –

@AmiTavory该问题询问渐近复杂性（在问题中使用大O表示法），所以我解释了为什么（以及何时）以这些术语来说，trie比数组更好。另外，我故意在答案中使用了*相对*来比较两个数组的选择。 – amit

尝试在较不常见的情况下确实有用。但他们有他们的用途。

假设你想实现一个自动完成者，例如，如你在一个文字处理器打字的东西，或引用在命令行的路径。然后，一个trie对于告诉你什么是给定前缀的子字符串非常有用。
假设你有一个真正长的字符串的字典，并且你想验证一个新的很长的字符串是否不在其中。然后，使用散列法，您需要查看新字符串的每个字母。使用一个trie，你可能会很快排除它。

来源

2015-06-27 09:00:44

回答

相关问题