c# - 排序列表或二叉搜索树

Question

如果搜索排序列表的复杂度为 O(log2 n) 并且搜索平衡的 BST 的复杂度也为 O(log2 n)，我应该使用哪一个假设如下:

1. 元素将在未排序的情况下接收，然后在加载所有元素后排序
2. 不会删除任何元素

应该使用哪个以及为什么(排序列表或二叉搜索树)？

谢谢。

Answer 1

如果您对数据进行一次排序然后只进行搜索，那么这两种方法的渐近复杂度将相同。

我认为排序列表的实际运行时间和内存消耗要低得多，索引到数组中非常快。

话虽这么说，也许使用哈希表对您来说会更好。创建它是 O(n)(与之前方法的 O(n log n) 相比)并且检索一个项目是 O(1)(与 O(log n) 相比)。