Finding Nearest Larger Neighbors
Finding Nearest Larger Neighbors
复制标题
寻找最近的较大邻居
DOI：
10.1007/978-3-642-03456-5_17
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
D. Kirkpatrick
中科院分区：
文献类型：
--
作者：
T. Asano;S. Bereg;D. Kirkpatrick
设计和分析有效的算法在实际应用中很重要，但它也很有趣，而且经常具有指导性，即使对于没有直接应用的简单问题也是如此。在这篇自成体系的论文中，我们试图传达一些算法设计和分析的乐趣。希望读者也会发现这个讨论很有启发意义。我们把注意力集中在一个问题上，我们称之为所有最近较大的邻居问题。为这个问题设计算法的部分乐趣在于，在略有不同的优化标准下出现了丰富的各种算法。我们还说明了几种重要的分析技术，包括摊销和使用非平凡循环不变量的正确性论证。我们希望以这种谦虚的方式，反映我们对Kurt Mehlhorn在算法设计和分析的理论、实践和欣赏方面的许多贡献的深深钦佩。
Designing and analysing efficient algorithms is important in practical applications, but it is also fun and frequently instructive, even for simple problems with no immediate applications. In this self-contained paper we try to convey some of fun of algorithm design and analysis. Hopefully, the reader will find the discussion instructive as well.We focus our attention on a single problem that we call theAll Nearest Larger Neighbors Problem. Part of the fun in designing algorithms for this problem is the rich variety of algorithms that arise under slightly different optimization criteria. We also illustrate several important analytic techniques, including amortization, and correctness arguments using non-trivial loop invariants.We hope, in this modest way, to reflect our deep admiration for the many contributions of Kurt Mehlhorn to the theory, practice and appreciation of algorithm design and analysis.