algorithm - 非随机访问结构中二进制搜索的复杂性

Question

对排序数组执行二分查找具有O(logN)复杂性，其中 N 是数组中元素的数量。
但是，如果我们在排序（链接）列表中执行二进制搜索，那么复杂性是多少？
我们正在logN对范围的中间元素进行比较，但要达到范围，复杂性是O(N)由于列表不是随机访问结构这一事实。
时间复杂度也是如此：
1）logN * O(N) = O(N)视为logN常数？或
2）在所有情况下都 logN*O(N) = O(NlogN)意味着什么？logN = O(logN)

这里什么是正确的？1 还是 2？

标签： algorithmdata-structuresbig-ocomplexity-theorybinary-search

Answer 1

第二个假设是正确的，第一个是错误的。渐近分析处理增长。如果节点数量增加，log(n) 也会增加。你不能把它当作一个常数。对于一个非常基本的示例，如果您有 10 个节点并且执行需要 10 秒，假设 100 个节点执行需要 200 秒似乎比假设 100 秒更准确（通过忽略 log(n)）。