前缀树的空间复杂度

Question

给定一个urls数组，如果存储在前缀树中，那么空间复杂度是多少？(Big-O，Big-Theta，Big-Omega)。数组的长度为n。

另外，如果使用基数树进行优化，Big-O会发生变化吗？

Answer 1

它将占用O(n)个空间...但是每个URL有10个字节和100个字节之间有很大的区别！

使用一个经过仔细编码的基数树，如果你的URL有很多共同的前缀，你可以期望在数组中比原始存储节省大量的空间(50%左右)。例如，如果它们是由爬虫程序生成的，就会出现这种情况。