在我看来,线性搜索实际上不是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和存储单元之间的有效接口而言,晶体管分布在球体中的情况是最佳方式.
