为什么仍然宣传线性搜索的时间复杂度为O(N)？

Question

在我看来,线性搜索实际上不是O(N),因为必须处理缓存未命中.这让我想知道为什么线性搜索仍然被宣传为具有时间复杂度O(N)？难道不应该考虑存储器单元与CPU的"距离"吗？除了由于光速而导致的信号传播是没有人可以逃脱的物理限制.在这里,我正在讨论经典,而不是量子计算.

让我们快速分析一下现实世界中线性搜索算法的合理界限.让我们假设一个无限小的CPU被封装在球形质量的存储单元的中心.使用恒定数量的晶体管k来实现每个单元.每单位体积的晶体管数量是rho.CPU具有读/写线和每个存储单元的数据线(假设路由这些线路不是问题),并且CPU只能在任何时刻读/写一个位.在这里,我们需要找到在N个存储位上执行线性搜索所需的时间.

(没有足够的代表发布图像,但这里是一个图表的链接,我试图说明问题) http://img51.imageshack.us/img51/7361/searchqn.png

球体半径

所需的总体积为N*k/rho.给定包含所有存储单元所需的球的半径为R,我们得到(4/3)*pi*R ^ 3 = N*k/rho,或者R = a*N ^(1/3)一些常数a.

元素壳dV(r)

考虑元素壳dV(r)= 4*pi*r ^ 2*dr(图中的灰色壳),其中包含驻留在其中的dV*rho/k存储位.CPU需要不小于2*r/c的时间来读取/更新驻留在该dV内的存储器位(首先断言R/W线,然后期望来自存储器单元的响应),其中c是速度光

整合dt

与dV(r)中的所有存储器单元接口所花费的时间由dt =(以dV为单位的单元数)*(与每个单元接口所花费的时间)=(8*pi*rho*r ^ 3*dr) /(k*c)= b*r ^ 3*dr为某些常数b.所用的总时间T将是b*r ^ 3相对于r的积分r = 0..a*N ^(1/3),这给出了T =(b*a ^ 4*N) ^(4/3))/ 4 = O(N ^(4/3)).

我不认为这种分析是过度的,因为现在计算机系统中的三级缓存并不罕见.很快(谁知道)可能存在多层存储器模型,其中存储器单元与CPU的距离可以被认为是连续的.

PS:对于那些感兴趣的人,存储单元线性布局并均匀布置在圆盘上的情况的时间复杂度分别为O(N ^ 2)和O(N ^(3/2)).我认为,就CPU和存储单元之间的有效接口而言,晶体管分布在球体中的情况是最佳方式.

Answer 1

算法是基于理论的,时间复杂度是在类似图灵机的基础上计算的,其中存储器本身被认为不同于标准计算机(以及处理存储器和操作的许多其他自动机不同).复杂性描述了一种模式,在给定一组应该完成的基本指令的情况下,基本操作将用于计算问题的答案.因此,时间复杂度为O(n).您所说的复杂性大多是非常精细的优化,除非您在非常具体的时间做某些事情,否则这些优化并不是必需的.当您确定要使用的算法时,这种分析没有标准算法分析那么多的含义.

就我而言,我会更关心这些细粒度数据,这些数字根据CPU和其他因素的不同而有所不同,并考虑到能够更快地实现我需要的东西.这些被称为微优化,它们只是为了利用硬件特定的变化,通常应该保留到最后.在大多数情况下,所有或大多数硬件将表现出相同或接近相同的复杂性(存在一些例外,例如SSE优化).