performance - 对数增长

Question

可能重复：
Big O 的简单英文解释

关于对数增长的维基百科文章是一个存根。我在stackoverflow上读到的许多答案都澄清了一个过程或函数是如何基于对数函数使用的0（我假设[见下文]它是0 [零]而不是O [作为M，N，O的字母,P,Q]，但如果它是错误的，请更正我的假设）和一个nor N。

有人可以更好地解释与常见计算解释有关的对数解释吗？也许以秒为单位的时间（也欢迎毫秒，只是试图在现实生活中的时间差异中概念化它......），大小和/或重量方面？

我经常看到以下内容：（请随意包括其他内容）

• O(1)
• 在）

我的假设是基于代码块外部的 0 [零] 没有斜杠，而inside a code block a 0 does have a slash through it.

Answer 1

这意味着执行时间（或其他资源）是数据量的某种函数。假设你需要 5 分钟才能炸毁 10 个气球。如果函数是 O(1)，那么炸掉 50 个气球也需要 5 分钟。如果是 O(n)，那么炸掉 50 个气球需要 25 分钟。

O(log n) 意味着随着事情的扩大，管理更大的 n 变得更容易（它遵循对数增长）。假设您想在 f(n) 个项目的目录中找到一个地址。假设搜索一个包含 100 个条目的目录需要 6.64 秒。[6.64 = log_2(100)] 那么搜索 200 个条目可能只需要 7.64 秒。这就是逻辑增长。