Uma Nova Proposta para a Obtenção da Complexidade de Pior Caso do ShellSort

ABSTRACT The worst-case time-complexity of the ShellSort, a comparison sorting algorithm, depends on a sequence of steps given as input. Each step consists of an integer representing an index offset of the pairs of elements that should be compared during the sorting of an input array. Such a complexity is known only to some specific sequences. In this work, we use a relation between the ShellSort and Frobenius number to present a new algorithm that provides an upper bound on the number of comparisons that ShellSort performs, for any given array and sequence of steps. We apply this algorithm, together with an empirical complexity analysis, to study sequences whose worst-case complexities are known through analytical method. We show that the empirical approach succeeded in determining such complexities. Based on such positive results, we extend the study to sequences for which the worst-case complexities are unknown.

摘要 希尔排序（ShellSort）是一种比较类排序算法，其最坏情况时间复杂度取决于输入的步长序列。每个步长由一个整数表示，对应对输入数组进行排序时，需比较的元素对的索引偏移量。目前仅针对部分特定序列，可确定其对应的最坏情况时间复杂度。本文通过建立希尔排序与弗罗贝尼乌斯数（Frobenius number）之间的关联，提出了一种新算法，可针对任意给定数组与步长序列，给出希尔排序执行比较操作的次数上界。我们将该算法与经验复杂度分析相结合，针对可通过解析方法确定最坏情况复杂度的序列展开研究，并证实该经验方法可有效确定此类序列的最坏情况复杂度。基于上述积极结果，我们将研究拓展至尚未明确最坏情况复杂度的序列。