java - n 个元素的时间复杂度

Question

我有这两个问题，我一直坚持。我对搜索的工作原理有所了解，但并不完全确定。我写了我所知道的，但我认为它似乎不是 100% 准确或回答了问题。

1) 第一次在 n 个元素的数据集上运行算法 A；它比算法 B 快。第二​​次在 n 个元素的数据集上运行算法 A；它比算法 B 慢。解释这是怎么可能的。举一个算法A和算法B的例子。

2）如果两者都有n个节点并且从最小到最大排序，那么在排序的链表或最小级别的BST中找到最大值会更快吗？解释。

这就是我对上述问题的看法。如果我错了或缺少任何关键信息，请纠正我。

1) 算法 A 是线性搜索（检查每个元素是否匹配）。算法 B 在使用二进制搜索之前对数据进行排序并存储在内存中。对于每个后续搜索，算法 B 会更快，因为二进制搜索通常比线性搜索更快。

2) 如果列表从 min 到 max 排序，如果你还有尾指针，它将变为 O(1)。原因是最大元素是链表中的最后一个。因此，您必须遍历尾部（O（n））。

对不起，如果我违反了任何规则，但我在很长一段时间后才问。

任何帮助，将不胜感激。谢谢你。

标签： javaalgorithmbinary-search-treenodes

Answer 1

我认为你的猜测是正确的。为了完整起见，您可以为二进制搜索添加 O(log(n))。