Suppose an algorithm that processes an array is O (log n). The algorithm takes at most 12 µs to process an array of size 25. All conditions being equal, approximately, at most how long will the algorithm take to process an array of size 625?
我是否可以通过除以 625/25 = 25 然后乘以每 25 个元素所需的 12 微秒((625/25)*12 = 300 微秒)来解决这个问题，还是还有更多？例如，我是否需要使用 log2(625) + 1 计算最大比较次数并在计算中使用它？感谢您的帮助。
编辑:这不是作业问题。
最佳答案
如果算法花费 O(log n) 时间，那么它需要 C log n + f( n) 处理 n 个元素的时间。这里 C 是一些常数因子，f(n) 是一些增长速度比 O(log n 慢的函数).
缩放目的最坏的情况是 f(n) 项没有任何贡献——即，当 f(n ) = 0——让我们忘掉这个词吧。我们只考虑 C log n。
我们知道
C log 25 = 12µs
因此
C = 12µs / log 25
现在如果我们插入 625，我们得到:
C log n = (12µs / log 25) log 625 = 24µs
(我的回答中的假设是 f(n)总是非负的并且单调递增。这不是 Big-O 符号的数学要求，但实际上这是一个合理的限制。)
关于java - 如何计算大小为 625 的数组的 O(log n) 处理时间？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40389561/