期望时间效率

Question

我有两个数据库文件，我必须搜索其中的一个，我使用了4种方法，即:内存中顺序，内存中二进制，磁盘顺序和磁盘二进制。需要搜索的文件大小为20Kb。这4个程序的预期运行时间应该是

disk sequential > disk binary > in-memory sequential > in-memory binary，但它将会是disk binary > disk sequential > in-memory sequential > in-memory binary。

磁盘二进制文件比磁盘顺序文件多花费大约1.5秒。为什么会这样呢？我计算的时间是在打开文件之前打印时间，然后在打开文件并执行搜索之后打印时间。

谢谢!

Answer 1

这取决于你的文件有多小；磁盘和主内存不一样，它是分块的，你的文件不会超过20个块。

因此log_2(20)大约是5，那么二进制搜索不会更好，除非您要搜索的内容在第五个块之后。