O（n）和O（log（n））之间的区别

本文介绍了O（n）和O（log（n））之间的区别-哪个更好，O（log（n））到底是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

这是我的第一门数据结构课程，每次讲座/ TA讲座，我们谈论的是 O（log（n））。这可能是一个愚蠢的问题，但如果有人可以向我确切解释这是什么意思，我将不胜感激！？

This is my first course in data structures and every lecture / TA lecture , we talk about O(log(n)) . This is probably a dumb question but I'd appreciate if someone can explain to me exactly what does it mean !?

推荐答案

它表示所讨论的事物（通常是运行时间）的缩放方式与其输入大小的对数一致。

It means that the thing in question (usually running time) scales in a manner that is consistent with the logarithm of its input size.

Big-O表示法并不表示 exact 方程，而是 bound 。例如，以下函数的输出均为O（n）：

Big-O notation doesn't mean an exact equation, but rather a bound. For instance, the output of the following functions is all O(n):

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

因为随着增加x，它们的输出全部呈线性增加-如果 f（n）和 g（n）， f（10 * n）和 g（10 * n）依此类推。

Because as you increase x, their outputs all increase linearly - if there's a 6:1 ratio between f(n) and g(n), there will also be approximately a 6:1 ratio between f(10*n) and g(10*n) and so on.

关于 O（n）或 O（log n）更好，请考虑：如果 n = 1000 ，则 log n = 3 （对于log-base-10）。您宁愿算法运行1000秒还是3秒？

As for whether O(n) or O(log n) is better, consider: if n = 1000, then log n = 3 (for log-base-10). Which would you rather have your algorithm take to run: 1000 seconds, or 3 seconds?