将算法从 O(2N) 优化到 O(N) 会使它的速度提高一倍吗?
Does optimizing an algorithm from O(2N) down to O(N) make it twice as fast?
在Big-O Notation中,O(N)和O(2N)描述了相同的复杂度。也就是说,O(2N) 的算法的时间或 space 复杂度的增长率基本上等于 O(N)。这一点在与给定极大 N 值的复杂度为 O(N^2) 的算法相比时尤其明显。O(N) 线性增加,而 O(N^2) 以二次方式增加。
所以我理解为什么 O(N) 和 O(2N) 被认为是相等的,但我仍然不确定是否将这两者视为完全相等。在一个输入数量 N 为 100 万或更多的程序中,在我看来,将时间复杂度减半实际上会节省大量时间,因为该程序可能会减少数百万个要执行的操作。
我正在考虑一个包含两个 for 循环的程序。每个 for 循环遍历一个非常大的 N 元素数组的整个长度。该程序的复杂度为 O(2N)。 O(2N) 减少到 O(N),但我觉得只需要一个 for 循环而不是两个的实现会使它成为一个更快的程序(即使单个 for 循环实现为了速度而牺牲了一些功能,例如)。
我的问题:
如果您有一个时间复杂度为 O(2N) 的算法,将其优化为具有 O(N) 时间复杂度会使它的速度提高一倍吗?
换句话说,将复杂度为 O(2N) 的算法优化为复杂度复杂度 O(N) 是否有显着的好处?我想程序的速度会有所提高,还是会因为 O(2N) == O(N)?
时间复杂度与速度不同。对于给定大小的数据,具有 O(N)
的程序可能比 O(2N)
更慢、更快或相同。此外,对于给定大小的数据,O(N)
可能比 O(N^2)
.
更慢、更快或相同
所以如果 Big-O 没有任何意义,我们为什么还要谈论它?
Big-O 表示法描述了随着数据大小的增加程序的行为。此行为始终是 相对的 。换句话说,Big-O 告诉你渐近曲线的形状,但不告诉你它的尺度或维度。
假设您有一个程序 A O(N)
。这意味着处理时间将与数据大小成线性比例(忽略可能使 运行 时间更像分段线性的缓存大小等现实世界的复杂性):
- 1000 行需要 3 秒
- 2000 行需要 6 秒
- 3000 行需要 9 秒
另一个程序 B 也是 O(N)
:
- 1000 行需要 1 秒
- 2000 行需要 2 秒
- 3000 行需要 3 秒
显然,第二个程序每行快 3 倍,即使它们都有 O(N)
。直观地,这告诉您两个程序都遍历每一行并花费一些固定时间来处理它。从 2000 到 1000 的时间差与从 3000 到 2000 的时间差相同 - 这意味着 线性增长 ,换句话说 一条记录所需的时间不会取决于所有记录的数量。这相当于程序执行某种 for
循环,例如在计算数字总和时。
而且,由于程序不同并且做的事情也不同,所以将程序 A 的 1 秒时间与程序 B 的 1 秒时间进行比较没有任何意义。你会比较苹果和橘子。这就是为什么我们不关心常数因子,我们说 O(3n)
等价于 O(n)
.
现在想象第三个程序C,它是O(N^2)
。
- 1000 行需要 1 秒
- 2000 行需要 4 秒
- 3000 行需要 9 秒
这里3000和2000之间的时间差比2000和1000之间的时间差大。数据越多,增加越大。这等效于在 for
循环中执行 for
循环的程序 - 例如,在搜索数据对时。
当你的数据很小的时候,你可能不在乎1-2秒的差异。如果你只是从上面的时间比较程序 A 和 C,而不了解底层行为,你可能会说 A 更快。但是看看更多记录会发生什么:
- 对于 10000 行程序 A 将花费 30 秒
- 对于 10000 行程序 C 将花费 1000 秒
- 对于 20000 行程序 A 将花费 60 秒
- 对于 20000 行程序 C 将花费 4000 秒
最初,相同数据的相同性能很快变得非常明显 - 几乎是 100 倍。在这个世界上,运行ning C 在更快的 CPU 上是不可能跟上 A 的,而且数据越大,这就越是真实的。与众不同的是 可扩展性 。这意味着要回答诸如 1 年后数据库将增长到其大小的两倍时我们需要多大的机器 之类的问题。使用 O(N)
,您通常没问题 - 您可以购买更多服务器、更多内存、使用复制等。使用 O(N^2)
,您通常可以达到一定规模,此时购买任意数量的新机器将不足以解决您的问题,您将需要在软件中找到不同的方法,或者 运行 在 GPU 集群等大规模并行硬件上找到它。使用 O(2^N)
除非你能以某种方式将数据的最大大小限制在仍然可用的范围内,否则你就完蛋了。
请注意,以上示例是理论上的,并有意简化;正如@PeterCordes 指出的那样,由于缓存、分支预测错误、数据对齐问题、矢量操作和数百万其他特定于实现的细节,真实 CPU 上的时间可能会有所不同。请在下面的评论中查看他的链接。
在Big-O Notation中,O(N)和O(2N)描述了相同的复杂度。也就是说,O(2N) 的算法的时间或 space 复杂度的增长率基本上等于 O(N)。这一点在与给定极大 N 值的复杂度为 O(N^2) 的算法相比时尤其明显。O(N) 线性增加,而 O(N^2) 以二次方式增加。
所以我理解为什么 O(N) 和 O(2N) 被认为是相等的,但我仍然不确定是否将这两者视为完全相等。在一个输入数量 N 为 100 万或更多的程序中,在我看来,将时间复杂度减半实际上会节省大量时间,因为该程序可能会减少数百万个要执行的操作。
我正在考虑一个包含两个 for 循环的程序。每个 for 循环遍历一个非常大的 N 元素数组的整个长度。该程序的复杂度为 O(2N)。 O(2N) 减少到 O(N),但我觉得只需要一个 for 循环而不是两个的实现会使它成为一个更快的程序(即使单个 for 循环实现为了速度而牺牲了一些功能,例如)。
我的问题:
如果您有一个时间复杂度为 O(2N) 的算法,将其优化为具有 O(N) 时间复杂度会使它的速度提高一倍吗?
换句话说,将复杂度为 O(2N) 的算法优化为复杂度复杂度 O(N) 是否有显着的好处?我想程序的速度会有所提高,还是会因为 O(2N) == O(N)?
时间复杂度与速度不同。对于给定大小的数据,具有 O(N)
的程序可能比 O(2N)
更慢、更快或相同。此外,对于给定大小的数据,O(N)
可能比 O(N^2)
.
所以如果 Big-O 没有任何意义,我们为什么还要谈论它?
Big-O 表示法描述了随着数据大小的增加程序的行为。此行为始终是 相对的 。换句话说,Big-O 告诉你渐近曲线的形状,但不告诉你它的尺度或维度。
假设您有一个程序 A O(N)
。这意味着处理时间将与数据大小成线性比例(忽略可能使 运行 时间更像分段线性的缓存大小等现实世界的复杂性):
- 1000 行需要 3 秒
- 2000 行需要 6 秒
- 3000 行需要 9 秒
另一个程序 B 也是 O(N)
:
- 1000 行需要 1 秒
- 2000 行需要 2 秒
- 3000 行需要 3 秒
显然,第二个程序每行快 3 倍,即使它们都有 O(N)
。直观地,这告诉您两个程序都遍历每一行并花费一些固定时间来处理它。从 2000 到 1000 的时间差与从 3000 到 2000 的时间差相同 - 这意味着 线性增长 ,换句话说 一条记录所需的时间不会取决于所有记录的数量。这相当于程序执行某种 for
循环,例如在计算数字总和时。
而且,由于程序不同并且做的事情也不同,所以将程序 A 的 1 秒时间与程序 B 的 1 秒时间进行比较没有任何意义。你会比较苹果和橘子。这就是为什么我们不关心常数因子,我们说 O(3n)
等价于 O(n)
.
现在想象第三个程序C,它是O(N^2)
。
- 1000 行需要 1 秒
- 2000 行需要 4 秒
- 3000 行需要 9 秒
这里3000和2000之间的时间差比2000和1000之间的时间差大。数据越多,增加越大。这等效于在 for
循环中执行 for
循环的程序 - 例如,在搜索数据对时。
当你的数据很小的时候,你可能不在乎1-2秒的差异。如果你只是从上面的时间比较程序 A 和 C,而不了解底层行为,你可能会说 A 更快。但是看看更多记录会发生什么:
- 对于 10000 行程序 A 将花费 30 秒
- 对于 10000 行程序 C 将花费 1000 秒
- 对于 20000 行程序 A 将花费 60 秒
- 对于 20000 行程序 C 将花费 4000 秒
最初,相同数据的相同性能很快变得非常明显 - 几乎是 100 倍。在这个世界上,运行ning C 在更快的 CPU 上是不可能跟上 A 的,而且数据越大,这就越是真实的。与众不同的是 可扩展性 。这意味着要回答诸如 1 年后数据库将增长到其大小的两倍时我们需要多大的机器 之类的问题。使用 O(N)
,您通常没问题 - 您可以购买更多服务器、更多内存、使用复制等。使用 O(N^2)
,您通常可以达到一定规模,此时购买任意数量的新机器将不足以解决您的问题,您将需要在软件中找到不同的方法,或者 运行 在 GPU 集群等大规模并行硬件上找到它。使用 O(2^N)
除非你能以某种方式将数据的最大大小限制在仍然可用的范围内,否则你就完蛋了。
请注意,以上示例是理论上的,并有意简化;正如@PeterCordes 指出的那样,由于缓存、分支预测错误、数据对齐问题、矢量操作和数百万其他特定于实现的细节,真实 CPU 上的时间可能会有所不同。请在下面的评论中查看他的链接。