O (n)和 O (log (n))的区别——哪个更好? O (log (n))到底是什么？

这是我在数据结构方面的第一堂课，每堂课/助教课，我们都会谈到 O(log(n))。这可能是一个愚蠢的问题，但我希望有人能向我解释到底是什么意思! ？

124001 次浏览
小开
最佳答案

它意味着所讨论的事物(通常是运行时间)以一种与其输入大小的对数一致的方式进行扩展。

大 O 符号 并不意味着一个 一模一样方程，而是一个 约束。例如，下列函数的输出都是 O (n) :

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

因为随着 x 的增加，它们的输出都呈线性增加-如果 f(n)和 g(n)之间的比例为6:1，那么 f(10*n)和 g(10*n)之间的比例也将大约为6:1，以此类推。

至于 O(n)还是 O(log n)更好，考虑一下: 如果是 n = 1000，那么是 log n = 3(对于 log-base-10)。您希望您的算法运行哪一个: 1000秒还是3秒？

小开

Http://en.wikipedia.org/wiki/big_oh

O (log n)更好。

小开

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

基本上，O (something)是算法指令数(原子指令)的上界。因此，O (logn)比 O (n)更紧密，在算法分析方面也更好。但是所有的算法都是 O (logn)也是 O (n) ，但不是向后的..。

小开

对于大小 n的输入，O(n)的算法将执行与 n成正比的步长，而 O(log(n))的算法将执行与 log(n)大致相同的步长。

显然 log(n)比 n小，因此复杂度 O(log(n))的算法更好，因为它会更快。

小开

正式定义:

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。

小开

对于简短的答案，O (logn)比 O (n)好

O (log n)到底是什么？

一般来说，在引用大 O 表示法时，登录指的是以2为底的对数(与 进去表示以 e 为底的对数相同)。这个以2为底的对数是指数函数的反数。 一个指数函数非常快，我们可以直观地推断，它的反向会做完全相反的事情，即非常缓慢的 成长。

比如说

X = O (log n)

我们可以表示 n 为,

N = 2 < sup > x

还有

210 = 1024 & rarr; lg (1024) = 10

220 = 1,048,576 & rarr; lg (1048576) = 20

230 = 1,073,741,824 & rarr; lg (1073741824) = 30

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

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

Log2n 的一个因子应该在任何时候取代 n 的一个因子。

为了进一步巩固这一点，我在 解锁的算法中遇到了一个例子

考虑两台计算机: A 和 B

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

计算机 A-这台计算机每秒可以执行10亿条指令，并且可以使用复杂度为 O (n)的算法执行上述任务。我们可以估算出这台计算机完成任务所需要的时间

N/(指令 p 秒) & rarr; 107/10 ^ 9 = 0.01秒

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

Log (n)/(指令 p second) & rarr; log (107)/107.0.000002325349

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

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


提交答案