哪种复杂性更好？
假设一个图有N个节点和M条边，总迭代次数为k。(k是一个常数整数，大于1，独立于N和M)
设D=M/N是图的平均度。
我有两个基于图的迭代搜索算法。
第一种算法的复杂度为O(D^{2k})时间。
第二种算法具有O(k*D*N)时间复杂度。
根据它们的大O时间复杂度，哪一个更好？
有些人告诉我，第一种方法更好，因为图中的节点数N通常比现实世界中的D多得多。
其他人说第二个更好，因为第一个的k是指数增加的，但是第二个是线性增加的。
回答 3
Stack Overflow用户
发布于 2014-05-16 00:22:03
摘要
你的两个O都不能支配另一个，所以正确的方法是根据输入来选择算法
O支配地位
- 在
D<1(稀疏图)和相似的情况下更好。 - 在
D相对较大的情况下
更好
算法选择
重要的参数不仅是O，而且是它前面的实际常量。例如，实际上是100000*n的O(n)算法比当n<100000时仅为n^2的O(n^2)算法更差。
因此，给定图和期望的迭代次数k，您需要估计每个算法的预期性能，并选择最佳算法。
Stack Overflow用户
发布于 2014-05-16 12:36:00
大O表示法描述了函数在其参数增长时是如何增长的。因此，如果你想估计算法时间消耗的增长，你应该首先估计D和N将如何增长。这需要来自您的域的一些附加信息。
如果我们假设N无论如何都会增长。对于D，您有几个选择：
D保持不变-第一个算法肯定是betterD与N成比例增长-第二个算法是better
更一般的情况是:如果D的增长速度比N^(1/(2k-1))快，则应该选择第一种算法，否则选择第二种算法。
Stack Overflow用户
发布于 2015-04-24 21:53:05
对于每个固定的D，D^(2k)是一个常数，因此如果M足够大，第一个算法将击败第二个算法。然而，什么足够大取决于D。如果D不是常量或有限的，这两个复杂性是无法比较的。
在实践中，您将实现这两种算法，找到它们的实际速度的最佳近似值，并根据您的值选择速度更快的算法。
https://stackoverflow.com/questions/23683327
复制相似问题
腾讯云开发者
