Rab*_*OTM 2 optimization big-o time-complexity micro-optimization space-complexity
在 Big-O 表示法中，O(N) 和 O(2N) 描述了相同的复杂度。也就是说，O(2N)的算法时间或空间复杂度的增长率本质上等于O(N)。尤其是与复杂度为 O(N^2) 的算法（给定极大的 N 值）相比，这一点尤其明显。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)。这意味着处理时间将与数据大小成线性比例（忽略现实世界的复杂性，例如缓存大小，这可能会使运行时间更像分段线性）：
对于另一个程序 B 也是O(N)：
显然，第二个程序每行速度快了 3 倍，尽管它们都有O(N). 直观上，这告诉您两个程序都会遍历每一行并花费一些固定的时间来处理它。从 2000 到 1000 的时间差与从 3000 到 2000 的时间差相同 - 这意味着线性增长，换句话说，一条记录所需的时间不取决于所有记录的数量。这相当于程序执行某种 afor循环，例如计算数字之和时。
而且，由于程序不同并且执行不同的操作，因此将程序 A 的 1 秒时间与程序 B 的 1 秒时间进行比较是没有任何意义的。你会比较苹果和橙子。这就是为什么我们不关心常数因子，我们说它O(3n)相当于O(n)。
现在想象第三个程序 C，它是O(N^2).
这里3000和2000之间的时间差异比2000和1000之间的差异更大。数据越多，增加越大。这相当于程序for在for循环中执行循环 - 例如在数据中搜索对时。
当你的数据很小时，你可能不在乎 1-2 秒的差异。如果您仅从上面的时间比较程序 A 和 C，而不了解底层行为，您可能会想说 A 更快。但是看看更多记录会发生什么：
最初，相同数据的相同性能很快变得非常明显 - 几乎提高了 100 倍。在这个世界上，在更快的 CPU 上运行 C 是不可能跟上 A 的，而且数据越大，这一点就越正确。最重要的是可扩展性。这意味着要回答这样的问题：一年后，当数据库大小将增长到原来的两倍时，我们将需要多大的机器。有了O(N)，您通常就可以了 - 您可以购买更多的服务器，更多的内存，使用复制等。有了 ，O(N^2)您通常可以达到一定的规模，此时购买任何数量的新机器都不足以解决您的问题您需要在软件中找到不同的方法，或者在大规模并行硬件（例如 GPU 集群）上运行它。除非O(2^N)你能以某种方式将数据的最大大小限制为仍然可用的东西，否则你就完蛋了。
请注意，上述示例是理论上的，并且是有意简化的；正如 @PeterCordes 指出的，由于缓存、分支错误预测、数据对齐问题、向量操作和数百万其他特定于实现的细节，真实 CPU 上的时间可能会有所不同。请在下面的评论中查看他的链接。
| 归档时间： |
|
| 查看次数： |
730 次 |
| 最近记录： |