logo标签列表

大O表示法是衡量内存需求还是仅仅速度？

algorithmcomplexity-theorybig-o
21

我经常听到人们谈论Big O，它可以将算法相互进行比较。

这是衡量时钟周期还是空间需求呢？

如果人们想根据内存使用量对算法进行对比，他们会使用什么指标呢？

1
这本来可以成为一个不错的愚人节玩笑。 - P Shved
8个回答
21
如果有人说："这个算法的时间复杂度是 O(n)"，他谈论的是速度。如果有人说："这个算法的空间复杂度是 O(n)"，他谈论的是内存。
如果他只说 "这个算法是 O(n)"，通常他在谈论速度（虽然如果他是在讨论内存时说的，那么他可能在谈论内存）。
如果你不确定某个人正在谈论哪一个方面，就问问他吧。
20

简短回答：你需要考虑时间复杂度和空间复杂度的“大O符号”。

详细回答：大O符号只是一种符号表示法，可以用于任何上下文中。

@SarahVessels，实际上这并不是真的，那么输入的 n 是指什么？ - Pacerier
16

大O符号是一种可以用来描述任何函数的数学工具。通常人们使用它来描述速度，但同样也可以用来描述内存使用。

此外，当我们使用大O符号来描述时间时，通常并不是直接讨论时钟周期。相反，我们计算“基本操作”（这些操作被隐含地假定需要花费恒定数量的周期）。

5
通常来说，算法的优劣是通过操作数量来体现速度的。通常情况下，算法在速度上的差异比内存使用更为明显。但是，在适当的情况下，您会看到关于内存使用的O()符号表示。
2

大O表示的是基于输入增长而复杂度增长的度量。两个时间复杂度都为O(n)的算法可能执行时间差异很大，但它们的增长与输入的增长成线性关系。

2

大O符号可用于描述任何两个量之间的关系。虽然它通常只用于计算机科学，但这个概念也可以适用于其他领域，比如物理学。例如，在给定大小的天线产生单位强度信号所需的功率量与距离的平方成正比，即O(d^2)，而不管天线的形状如何。如果天线的大小相对于距离很大，所需的增强可能是线性或次线性的，而不是二次的，但随着距离的增加，二次项将占主导地位。

1

Big O等量级被用来衡量一些东西的增长。

当有人说某物是O(N)时，它的增长速率不会超过线性。如果某物是Ω(N^2)，那么它的增长速率不会低于二次方。当某物是Θ(2^N)时，它的增长速率是指数级别。

那个东西可以是算法的时间需求、算法的空间，或者基本上和空间和时间都无关的任何事情。

例如，一些大规模并行算法通常通过可以运行在多少处理器上来衡量可伸缩性。一个特定的算法可能在O(N^2)时间内在O(N)处理器上运行。另一个算法可能在O(N)的时间内在O(N^2)处理器上运行。

相关问题

另请参阅

0

通常情况下，算法竞争的是时间，因此我通常会假设任何O语句都是时间。然而，完全可以进行空间比较。O可用于任何度量 - 我们通常使用速度是因为它通常最重要。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接