performance - 假设需要 f(n) 微秒，可在一秒钟内解决的最大难题？

Question

我有这个问题：

f(n) = log(n) (it's log base 2 btw)

假设问题需要 f(n) 微秒，可以在一秒钟内解决的问题的最大大小 n 是多少？

好吧，因为 f(n) 是 log(n)，所以问题需要 log(n) 微秒，对吧？一秒钟有一百万微秒，对吧？所以我这样设置：

log(n) = 1000000

但这给出了 2^1000000 作为答案，这是一个绝对令人讨厌的巨大数字。难道我做错了什么？

Answer 1

没关系。O(log(n)) 算法非常快。

当然在现实生活中 f(n) 不会永远是 log(n)，如果你正在处理一些数据集，你会耗尽内存并开始撞击磁盘，这会很慢，并且稍后，您将用完地球上所有的磁盘空间...

Answer 2

你的数学是正确的。

在 log(n) 时间内运行的算法每次可以将问题的大小减半。一个例子是在二叉搜索树中查找一个项目。最坏的情况是，如果您要查找的物品位于其中一片叶子中。

所以每次你挑选一个孩子，你就砍掉了一半的树。一开始你有 2^1 000 000 个节点。当您向下一个子节点时，您有一半的节点，2^999 999。经过 100 万次操作后，您应该位于包含您正在寻找的节点的叶子节点。