将算法从 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 上的时间可能会有所不同。请在下面的评论中查看他的链接。