Selection on X1

被引：2

作者：

Kreitzberg, Patrick ^{[1
]}

Lucke, Kyle ^{[2
]}

Pennington, Jake ^{[1
]}

Serang, Oliver ^{[2
]}

机构：

[1] Univ Montana, Dept Math, Missoula, MT 59812 USA

[2] Univ Montana, Dept Comp Sci, Missoula, MT 59812 USA

来源：

PEERJ COMPUTER SCIENCE | 2021年

基金：

美国国家科学基金会;

关键词：

Selection; Cartesian product; Tree; Sorting; CONVOLUTION;

D O I：

10.7717/peerj-cs.483

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Selection on the Cartesian product is a classic problem in computer science. Recently, an optimal algorithm for selection on A+B, based on soft heaps, was introduced. By combining this approach with layer-ordered heaps (LOHs), an algorithm using a balanced binary tree of A+B selections was proposed to perform selection on X-1+X-2+...+X-m in o(n.m+k.m), where X-i have length n. Here, that o(n.m+k.m) algorithm is combined with a novel, optimal LOH-based algorithm for selection on A+B (without a soft heap). Performance of algorithms for selection on X-1+X-2+...+X-m are compared empirically, demonstrating the benefit of the algorithm proposed here.

引用

页数：11

共 14 条

[1] Necklaces, Convolutions, and X plus Y [J].