A sort of an adversary.

SODA '19: Symposium on Discrete Algorithms San Diego California January, 2019（2019）

引用 0|浏览90

暂无评分

摘要

We describe an efficient deterministic adversary that forces any comparison-based sorting algorithm to perform at least [MATH HERE] n log n comparisons. This improves on previous efficient adversaries of Atallah and Kosaraju (1981), Richards and Vaidya (1988), and of Brodal et al. (1996) that force any sorting algorithm to perform at least 1/2n log n comparisons.

查看译文

AI 理解论文

溯源树

样例

生成溯源树，研究论文发展脉络

Chat Paper

正在生成论文摘要