希尔排序时间复杂度的下界

发表于 分类于

论文 A Lower Bound on the Size of Shellsort Sorting Networks. Robert Cypher, 1989 阅读笔记。这篇文章证明了基于单调递减间隔序列的希尔排序的时间复杂度均为 Ω(nlog⁡2n/log⁡log⁡n)\Omega(n\log^2 n/\log \log n)。

一些符号

若不特殊说明，下文中的所有集合都是自然数集 N\mathbb N 的子集。

一个集合 TT 的补集记为：T‾=N−T\overline{T}=\mathbb N-T，它的第 ii 小元素记为 TiT_i。

对于任意实数 rr，定义这两个集合：Low(T,r)={v∈T∣v<r},High(T,r)={v∈T∣v≥r}\text{Low}(T,r)=\{v\in T\mid v<r\},\text{High}(T,r)=\{v\in T\mid v\ge r \}。

对于任意正整数 xx 与整数 yy，定义这样一个集合：Slice(T,x,y)={v∈T∣v≡y(modx)}\text{Slice}(T,x,y)=\{v\in T\mid v\equiv y\pmod x \}。

（后面先鸽子）