排序列表或二叉搜索树
本文关键字：搜索树 列表 排序 | 更新日期: 2023-09-27 18:15:12
如果搜索一个排序列表是O(log2 n)，搜索一个平衡的BST也是O(log2 n)，我应该使用哪一个假设如下:
- 元素将未排序接收，然后在所有元素加载后进行排序
- 不删除任何元素
哪个应该使用，为什么(排序列表或二叉搜索树)?
谢谢。
如果您对数据进行一次排序然后只进行搜索，那么两种方法的渐近复杂性将是相同的。
我认为排序列表将有更低的实际运行时间和内存消耗，索引到一个数组是非常快的。
话虽这么说，也许使用哈希表对你会更好。创建它是O(n)(与之前的方法的O(n log n)相比)，检索一个项目是O(1)(与O(log n)相比)。
设置两者(或所有三个)然后对它们进行基准测试是否过于困难?您可以使用包装器类从中抽象出数据结构，然后在两次基准测试之间更改包装器类。当然，我假设这里的时间是无限的。:)
它们都需要O(n log n)来创建/排序。所有的检索都是O(log n)
实际上，一个有序的二叉树可以表示为一个有序的数组，只要它是一个完全的完美树。所以它们在本质上是一样的