我对算法设计有一个非常基本和普遍的疑问。我已经学习了基本算法，现在正在学习随机算法。我观察到，教授主要专注于设计算法，最终将尝试降低复杂性。
通常的方法（我观察到的）是学习一些基本（或较旧的）算法，这些算法在复杂性方面表现不佳，因此目标是使用较新的算法修改较旧的算法，该算法应专注于降低复杂性，而不会影响输出。
但是在我研究过的大多数算法中，特别是分布式算法（在分布式操作系统中），例如分布式互斥算法，分布式死锁检测等，我观察到的是（而且我认为大多数情况下）算法的设计不应该只关注复杂性增强，还应该关注算法的完美。
让我们以分布式互斥算法为例。最基本的算法是Lamport算法，它的修改版本（通过增强复杂性）是Ricart-Agarwala算法。由于在分布式环境中，通信主要是通过消息传递来实现的，因此对于分布式互斥，我们有三种消息：a）请求关键资源b）回复请求c）释放关键资源。基本算法使用额外的发布消息（通知所有站点我的站点已释放关键资源，以便您可以输入）。但是在高级版本中，他们所做的是通过在回复消息中容纳这些发布消息来丢弃这些发布消息。因此，他们提出了一些降低复杂性的解决方案。
但是当我尝试在java中实现这些算法时，我观察到即使基本算法的复杂性更高，但它比高级算法更完美。因为通过减少传输的消息数量（在高级解决方案中），本地站点不再知道远程站点实际上是否释放了资源的事实，因为在确认释放消息时，只有站点更新其本地数据结构，例如请求队列等。如果我们不发送任何明确的发布通知，则在整个运行过程中，请求在本地站点的请求队列中不必要地保持挂起状态。
So my doubt is that if enhancement of complexity is so important, why can't perfection ? I mean if algorithm is producing perfect results at the cost of bit higher complexity then how does it matters as far as I am getting perfection in output as compared to the enhanced complexity solution which lacks in perfection ?
注意：完美并不意味着正确/不正确的结果。结果总是正确的。只有产生结果的完美程度或准确性会有所不同。
原则上，对产生完全相同输出的两个算法进行了公平的复杂性比较。例如排序。
在你的情况下，它是不同的，你描述具有不同行为的算法。
要选择更适合的算法，许多因素决定：
- 易于实现（在实践中非常重要）
- 一个更快的算法，缺乏一些功能，就像你的情况一样，必须非常快（预期数据量的faktor 10）来选择它，或者更容易实现。
- 鲁棒性：众所周知的算法，成功使用了 10 年，或者来自一篇论文的新算法，它很有可能只适用于科学家的环境（针对算法进行了优化）。 （我知道电信网络算法有这样的情况）
考虑任何NP完全问题（例如旅行推销员问题）。
对于这些问题，没有已知的非指数精确算法（特殊情况除外），因此实际上需要数年（或更长时间）才能为这些问题的任何合理大小版本找到确切的解决方案。
因此，相反，我们使用启发式和近似（可能还有一些随机性）在合理的时间范围内获得非精确解决方案。
NP完全问题只是一个极端的例子 - 我们也可以只有几秒钟的时间来获得解决方案（无论出于何种原因），但找到确切的解决方案将需要几分钟。因此，这一切都归结为平衡我们想要运行算法多长时间以及我们希望结果有多好（开发时间当然也起着作用）。
我希望我正确理解了您的问题，并且这会有所帮助。
与其说是"完美"，不如考虑"适合特定目的"。
对于分布式互斥算法的示例，请从不同的角度考虑"简单"和"改进"算法。 正如另一个答案指出的那样，这两种算法的行为不同; 我的观点是，不同的人对这种行为的不同方面感兴趣。
将算法用于特定目的的人可能并不关心其行为的所有方面。 对于您的示例，您担心挂起的资源锁。 但是，如果互斥算法预计一直运行，则用户可能不会关心，因为无论如何都会立即返回锁，同时使用的消息比简单版本少。 如果你想要效率和及时性，那么可能有一些方法可以同时容纳两者 - 以更大的复杂性为代价 - 如果你正在寻找实际的"完美"，这是逻辑端点。
计算机科学家不知道如何使用他的算法。 一般来说，他无法预测特定技术的所有可能变化，如果他可以的话，你不会想全部阅读它们！ 在发布算法时，表达的清晰度是你追求的"完美"——这个想法应该尽可能简单地描述。