在大-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),但是我觉得一个只需要一个循环而不是两个循环的实现会使它成为一个更快的程序(例如,即使一个循环实现为了速度而牺牲了一些功能)。
我的问题:
如果您有一个具有时间复杂度O(2N)的算法,那么优化它使O(N)时间复杂度提高一倍吗?
换句话说,优化O(2N)算法到O(N)是否有显著的好处?我想,程序的速度会有所提高,或者说,由于O(2N) == O(N),增加的速度是微不足道的,不值得付出这么大的努力吗?
发布于 2021-04-02 03:30:59
时间的复杂性和速度不一样。对于给定的数据大小,具有O(N)
的程序可能更慢、更快或与O(2N)
相同。另外,对于给定的数据大小,O(N)
可能更慢、更快或与O(N^2)
相同。
所以如果“大O”没有任何意义,我们为什么要谈论它呢?
大O表示法描述了随着数据大小的增加,程序的行为.这种行为总是相对的。换句话说,大O告诉你渐近曲线的形状,而不是它的尺度或维数。
假设你有一个程序A是O(N)
。这意味着处理时间将与数据大小成线性比例(忽略现实中的复杂情况,比如缓存大小,这可能使运行时间更像分段线性):
对于另一个程序B,也就是O(N)
显然,第二个程序每行的速度是3倍,尽管它们都有O(N)
。直观地,这告诉您,这两个程序贯穿每一行,并花费一些固定的时间来处理它。2000年至1000年间的时间差与3000到2000之间的差异相同--这意味着增长的线性,换句话说,一个记录所需的时间并不取决于所有记录的数量。这相当于程序执行某种for
-loop,例如,在计算数字和时。
而且,由于程序是不同的,做不同的事情,所以将程序A的1秒与程序B的1秒时间进行比较是没有任何意义的。你会比较苹果和橘子。这就是为什么我们不关心常数因子,我们说O(3n)
等同于O(n)
。
现在设想第三个程序C,即O(N^2)
。
这里3000到2000之间的时间差比2000年和1000之间的差大。数据越多,增幅就越大。这相当于在for
循环中执行for
循环的程序,例如,在数据中搜索对时。
当您的数据很小时,您可能不关心1-2秒的差异.如果您只是从上面的时间比较程序A和C,而不了解基本的行为,您可能会想说A更快。但是看看更多的记录会发生什么:
F 248
最初,相同数据的相同性能很快就变得非常明显--几乎是100倍。在这个世界上,没有一种方法可以在更快的CPU上运行C来跟上A,而且数据越大,这就越真实。让一切变得不同的是scalability.这意味着要回答这样的问题,比如一年后数据库将增长到两倍的时候,我们需要多大的一台机器。使用O(N)
,您通常可以购买更多的服务器、更多的内存、使用复制等等。使用O(N^2)
,您通常可以达到一定的大小,此时购买任何数量的新机器都不足以解决您的问题,您需要在软件中找到不同的方法,或者在大规模并行硬件(如GPU集群)上运行。对于O(2^N)
,除非您可以以某种方式将数据的最大大小限制在仍然可以使用的东西上,否则就会非常糟糕。
请注意,上面的示例是理论性的,并且是有意简化的;正如@PeterCordes所指出的,由于缓存、分支错误预测、数据对齐问题、向量操作和其他特定于实现的数百万个细节,实际CPU上的时间可能有所不同。请在下面的评论中看到他的链接。
https://stackoverflow.com/questions/66913864
复制相似问题