稀疏尺 稀疏尺Sparse ruler指的是去掉了一些刻度的尺子抽象来说一个长度为 L displaystyle L 有 m displaystyle m 个刻度的稀疏尺可以被记为整数序列 a   a       a m displaystyle aaam    a   a       a m  L displaystyle aaamL 刻度 a  displaystyle a 和 a m displaystyle am 对应尺子的首尾为了能够测量长度 K displaystyle K    K  L displaystyle leq Kleq L 我们需要存在刻度 a i displaystyle ai  a j displaystyle aj 使得 a j  a i  K displaystyle ajaiK  如果一个稀疏尺能够测量不超过它的长度的任意整数长度称这个稀疏尺是完全的对于一个完全稀疏尺如果不存在另一个长度相同但刻度数量更少的完全稀疏尺则称它是最小稀疏尺类似的如果不存在另一个刻度数量相同但长度更大的稀疏尺则称它是最大稀疏尺如果一个稀疏尺既是最大稀疏尺又是最小稀疏尺则称它是最优稀疏尺 对于 m displaystyle m 个刻度不同的刻度组合共有 m  m      displaystyle mm 种因此这是长度 L displaystyle L 的理论上界事实上只有在或个刻度的情况下可以取到该上界对于更多的刻度数量最优长度和理论上界的差距非均匀地逐渐增大 例如对于  个刻度的稀疏尺理论上界为 但实际上的最大长度为 长度为刻度数为的稀疏尺有三种可能的刻度选择其中之一是是      例如要测量的长度可以使用这把尺子的刻度和 格伦布尺是一种要求所有的 a j  a i displaystyle ajai 都不相等的稀疏尺通常 m displaystyle m 个刻度的格伦布尺将比 m displaystyle m 个刻度的最佳稀疏尺长得多因为 m  m      displaystyle mm 是格伦布尺长度的下界比较长的格伦布尺可能有间隙换句话说它可能有无法测量的距离例如最优格伦布尺       的长度为 但它无法测量长度  或