前缀树的空间复杂度

Question

给定一个url数组，如果存储在前缀树中，空间复杂度是多少？ （Big-O，Big-Theta，Big-Omega）。数组的长度是n。

如果使用基数树进行优化，那么Big-O也会改变吗？

Answer 1

这将需要O（n）空间......但每个URL和100个10字节之间有很大的区别！

使用经过仔细编码的基数树，如果您的URL具有大量通用前缀，则可以期望在数组中的原始存储上节省大量空间（50％ish）。例如，如果它们是由抓取工具生成的，则会是这种情况。