算法完善与时间分析 : Does Time complexity matters everytime?

Question

我对算法设计有一个非常基本和普遍的疑问。我已经学习了基本算法，现在正在学习随机算法。我到处观察到教授主要专注于设计最终会尝试降低复杂性的算法。

通常的方法(我观察到的)是学习一些在复杂性方面表现不佳的基本(或旧的)算法，因此目标是用更新的算法修改旧的算法，该算法应该侧重于降低复杂性，而不影响输出。

但在我研究过的大多数算法中，尤其是分布式算法(在分布式操作系统中)，例如分布式互斥算法、分布式死锁检测等算法，我观察到的是(而且大部分我认为)设计算法的研究不应只关注复杂度的提高，还应关注算法的完善。

举个分布式互斥算法的例子。最基本的算法是 Lamport 算法，它的修改版本(通过提高复杂性)是 Ricart-Agarwala 算法。由于在分布式环境中通信主要是通过消息传递，对于分布式互斥我们有三种消息:a)请求关键资源 b)回复请求 c)释放关键资源。基本算法使用额外的释放消息(通知所有站点我的站点已释放关键资源，因此您可以进入)。但在高级版本中，他们所做的是通过在回复消息中容纳这些发布消息来丢弃这些消息。因此他们提出了一些降低复杂性的解决方案。

但是当我尝试在java中实现这些算法时，我观察到即使基础算法的复杂度高了一点，但它比高级算法更完美。因为通过减少传输的消息数量(在高级解决方案中)，本地站点不再知道远程站点是否实际释放了资源这一事实，因为在确认释放消息后，只有站点更新其本地数据结构，例如请求队列等。如果我们不发送任何明确的发布通知，那么在整个运行过程中，请求将不必要地保留在本地站点的请求队列中。

所以我的疑问是，如果复杂性的增强如此重要，为什么不能完美呢？我的意思是，如果算法以更高的复杂度为代价产生完美的结果，那么与缺乏完美度的增强复杂度解决方案相比，我在输出中获得完美度有多重要？

注意:我所说的完美并不是指正确/不正确的结果。结果总是正确的。只是所产生结果的完美程度或准确性不同。

Answer 1

原则上，对产生完全相同输出的两种算法进行公平的复杂性比较。例如排序。

在你的情况下是不同的，你描述了具有不同行为的算法。

要选择更适合的算法，许多因素决定:

• 易于实现(在实践中非常重要)
• 一个更快的算法，它缺少一些功能，就像你的情况一样，必须非常快(预期数据量上的 faktor 10)才能选择它，或者更容易实现。
• 稳健性:众所周知的算法，已成功使用 10 年，或者论文中的新算法很有可能只适用于科学家的环境(针对算法进行了优化)。 (我知道电信网络算法的这种情况)