用于插入和搜索的特里数据结构的最佳/最差/平均情况复杂度(以 Big-O 表示法)是多少？
我认为是O(K)对于所有情况，其中 K是被插入或搜索的任意字符串的长度。有人会证实这一点吗？
最佳答案
根据 Wikipedia和 this source ，插入和搜索 trie 的最坏情况复杂度是 O(M)哪里M是 key 的长度。我找不到任何描述插入和搜索的最佳或平均情况复杂性的来源。但是，我们可以有把握地说，最佳和平均情况复杂度是 O(M)哪里M是键的长度，因为 Big-O 只描述了复杂性的上限。
关于data-structures - 什么是 Trie 数据结构的最佳/最差/平均情况 Big-O 运行时？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/17891442/