Chr*_*ris 17 theory algorithm computer-science data-structures
我正在寻找一种如此未知但有用的算法或数据结构,您认为这是计算机科学或编程社区的可怕疏忽.如果只有我们都可以学习这样一两件事,有很多好会做很多未来的计划.
我能想出的最好的是插值搜索,只有极少数程序员知道,而每个人都知道二进制搜索.我认为毫无疑问,快速搜索有序列表是一种非常有用且基本的算法.
这两者几乎完全相同 - 所以这不是问题.
它对均匀分布的数据执行O(log(log(n))),而不是二进制搜索O(log(n)).这意味着搜索40亿个数字只需要5个探测器而不是32个,那就更好了!
在非完美统一的数据上,它在大多数情况下仍然表现得非常好.只有当数据真正偏离时才会像二进制搜索一样糟糕或者更糟糕.当数据高度偏斜时,这是O(n)最坏的情况,但在大多数现实情况下这种情况非常罕见.
即便如此,人们也可以构造一个偶数/奇数算法来在两者之间交替,并得到最差的二分搜索情况,并使用插值搜索的平均情况来缓解极端情况.
大多数程序员/图书馆都忽略了这一点.
谁能打败那个人？