对已排序的数组执行二进制搜索具有O(logN)的复杂度，其中N是数组中元素的数量。但是，如果我们在排序（链接）列表中执行二进制搜索，那么复杂度是多少？我们正在对范围的中间元素进行logN比较，但要达到该范围，由于列表不是随机访问结构，因此复杂度为O(N)。时间复杂度也是如此：1）logN * O(N) = O(N)将logN视为常数？要么2）logN*O(N) = O(NlogN)表示在所有情况下都为logN = O(logN)？
这里正确吗？ 1还是2？
第二个假设是正确的，第一个假设是错误的。渐进分析处理增长。如果节点数增加，log（n）也将增加。您不能将其视为常量。对于一个非常基本的示例，如果您有10个节点并且花了10秒钟来执行，那么假设100个节点花200秒钟来执行似乎比假设100秒（忽略log（n））更准确。