我有这个问题：
f(n) = log(n) (it's log base 2 btw)
假设问题需要 f(n) 微秒，可以在一秒钟内解决的问题的最大大小 n 是多少？
好吧，因为 f(n) 是 log(n)，所以问题需要 log(n) 微秒，对吧？一秒钟有一百万微秒，对吧？所以我这样设置：
log(n) = 1000000
但这给出了 2^1000000 作为答案，这是一个绝对令人讨厌的巨大数字。难道我做错了什么？
问问题
1384 次
2 回答
3
没关系。O(log(n)) 算法非常快。
当然在现实生活中 f(n) 不会永远是 log(n)，如果你正在处理一些数据集，你会耗尽内存并开始撞击磁盘，这会很慢，并且稍后，您将用完地球上所有的磁盘空间...
于 2011-09-07T22:00:28.893 回答
3
你的数学是正确的。
在 log(n) 时间内运行的算法每次可以将问题的大小减半。一个例子是在二叉搜索树中查找一个项目。最坏的情况是，如果您要查找的物品位于其中一片叶子中。
所以每次你挑选一个孩子，你就砍掉了一半的树。一开始你有 2^1 000 000 个节点。当您向下一个子节点时，您有一半的节点，2^999 999。经过 100 万次操作后，您应该位于包含您正在寻找的节点的叶子节点。
于 2011-09-07T22:03:39.573 回答