algorithm - O(n) 和 O(log(n)) 之间的区别 - 哪个更好，O(log(n)) 到底是什么？

Question

这是我的第一门数据结构课程，也是我们谈论的每一堂课/助教课O(log(n))。这可能是一个愚蠢的问题，但如果有人能向我解释这到底是什么意思，我将不胜感激！？

score 105 · Accepted Answer

这意味着有问题的事物（通常是运行时间）以与其输入大小的对数一致的方式缩放。

Big-O 表示法并不意味着一个精确的方程，而是一个bound。例如，以下函数的输出都是 O(n)：

f(x) = 3x
g(x) = 0.5x
m(x) = x + 5

因为随着 x 的增加，它们的输出都会线性增加 - 如果和之间的比率为 6:1 ，则f(n)和之间的比率g(n)也约为 6:1 f(10*n)，g(10*n)依此类推。

至于是否O(n)更好O(log n)，请考虑： if n = 1000, then log n = 3（对于 log-base-10）。您希望算法运行哪个：1000 秒还是 3 秒？

score 38 · Accepted Answer

简而言之，O(log n) 优于 O(n)

现在 O(log n) 到底是什么？

通常，当提到大 O 表示法时，log n是指以 2 为底的对数，（同样的方式ln表示以 e 为底的对数）。这个以 2 为底的对数是指数函数的倒数。指数函数增长非常迅速，我们可以直观地推断出它的反函数会完全相反，即增长非常缓慢。

例如

x = O(log n)

我们可以将 n 表示为 ,

n = 2 ^x

和

2 ¹⁰ = 1024 → lg(1024) = 10

2 ²⁰ = 1,048,576 → lg(1048576) = 20

2 ³⁰ = 1,073,741,824 → lg(1073741824) = 30

n的大增量只会导致 log(n) 的非常小的增加

另一方面，对于 O(n) 的复杂度，我们得到线性关系

log ₂ n 的因数应随时超过 n 的因数。

考虑 2 台计算机：A 和 B

两台计算机都有一个任务是在数组中搜索一个值让我们假设数组有 1000 万个元素要搜索

计算机 A——这台计算机每秒可以执行 10 亿条指令，预计使用复杂度为 O(n) 的算法执行上述任务。我们可以将这台计算机完成任务所需的时间近似为

n/(指令 p 秒) → 10 ⁷ /10^9 = 0.01 秒

计算机 B - 这台计算机要慢得多，每秒只能执行 1000 万条指令。计算机 B 预计将使用复杂度为 O(log n) 的算法执行上述任务。我们可以将这台计算机完成任务所需的时间近似为

log(n) /(指令 p 秒) → log(10 ⁷ )/10 ⁷ = 0.000002325349

通过这张图，我们可以看到，尽管计算机 A 比计算机 B 好得多，但由于 B 使用的算法，它完成任务的速度要快得多。

我认为现在应该很清楚为什么 O(log(n)) 比 O(n) 快得多

score 21 · Accepted Answer

对于 size 的输入n，一个算法O(n)会按比例执行步骤n，而另一个算法O(log(n))会大致执行步骤log(n)。

显然log(n)小于n因此复杂度算法O(log(n))更好。因为它会快得多。

score 7 · Accepted Answer

O(logn) 表示算法的最大运行时间与输入大小的对数成正比。O(n) 表示算法的最大运行时间与输入大小成正比。

基本上，O(something) 是算法指令数量（原子指令）的上限。因此，O(logn) 比 O(n) 更严格，并且在算法分析方面也更好。但是所有 O(logn) 的算法也是 O(n)，但不是倒退...

score 5 · Accepted Answer

5

O(log n) 更好。

于 2012-04-29T04:04:28.587 回答

score 3 · Accepted Answer

正式定义：

g(x) = O(f(x)) <=> 有 x0 和常数 C，对于每个 x > x0，|g(x)| <= C|f(x)|。

因此，如果你发现问题 P 的算法 A 的复杂度为 O(f(n))，你可以说你的算法将执行的步骤数渐近地小于或等于 f(n)，而 n 通常是输入大小。（n 可以是任何东西）

进一步阅读：http://en.wikipedia.org/wiki/Big_O_notation。

6 回答 6