这里没有理论答案,但我写了一个快速的Java程序来探索运行时间行为作为k和n的函数,其中n是总位长度,k是1的数量。我和一些回答者一样认为,“常规”算法检查所有比特位置对并查找第三个比特,即使在最坏情况下需要O(k^2),但实际上由于最坏情况需要稀疏比特串,因此是O(n ln n)。
不管怎样,下面是程序。这是一个蒙特卡洛风格的程序,对于常数n运行大量的试验NTRIALS,并随机生成一系列k值的比特集合,使用指定的上下限约束在伯努利过程中的1的密度,并记录找到或未找到均匀间隔的三个1的运行时间,以步数而不是CPU时间来衡量。我对n=64, 256, 1024, 4096, 16384*(仍在运行)进行了测试运行,先进行500000次试验,以查看哪些k值需要最长的运行时间,然后进行另一次测试,进行5000000次试验,并缩小对单点密度的关注范围以查看那些数值的情况。最长的运行时间确实出现在非常稀疏的密度情况下(例如,对于n=4096,运行时间峰值在k=16-64范围内,平均运行时间在k=31时为4212步,最大运行时间在k=58时峰值为5101步)。看起来,要使最坏情况的O(k^2)步长超过扫描比特串以查找1的位置索引的O(n)步长,需要非常大的N值。
package com.example.math;
import java.io.PrintStream;
import java.util.BitSet;
import java.util.Random;
public class EvenlySpacedOnesTest {
static public class StatisticalSummary
{
private int n=0;
private double min=Double.POSITIVE_INFINITY;
private double max=Double.NEGATIVE_INFINITY;
private double mean=0;
private double S=0;
public StatisticalSummary() {}
public void add(double x) {
min = Math.min(min, x);
max = Math.max(max, x);
++n;
double newMean = mean + (x-mean)/n;
S += (x-newMean)*(x-mean);
mean = newMean;
}
public double getMax() { return (n>0)?max:Double.NaN; }
public double getMin() { return (n>0)?min:Double.NaN; }
public int getCount() { return n; }
public double getMean() { return (n>0)?mean:Double.NaN; }
public double getStdDev() { return (n>0)?Math.sqrt(S/n):Double.NaN; }
public static void printOut(PrintStream ps, StatisticalSummary[] statistics) {
for (int i = 0; i < statistics.length; ++i)
{
StatisticalSummary summary = statistics[i];
ps.printf("%d\t%d\t%.0f\t%.0f\t%.5f\t%.5f\n",
i,
summary.getCount(),
summary.getMin(),
summary.getMax(),
summary.getMean(),
summary.getStdDev());
}
}
}
public interface RandomBernoulliProcess
{
public void setProbability(double d);
public boolean getNextBoolean();
}
static public class Bernoulli implements RandomBernoulliProcess
{
final private Random r = new Random();
private double p = 0.5;
public boolean getNextBoolean() { return r.nextDouble() < p; }
public void setProbability(double d) { p = d; }
}
static public class TestResult {
final public int k;
final public int nsteps;
public TestResult(int k, int nsteps) { this.k=k; this.nsteps=nsteps; }
}
final private int n;
final private int ntrials;
final private double pmin;
final private double pmax;
final private Random random = new Random();
final private Bernoulli bernoulli = new Bernoulli();
final private BitSet bits;
public EvenlySpacedOnesTest(int n, int ntrials, double pmin, double pmax) {
this.n=n; this.ntrials=ntrials; this.pmin=pmin; this.pmax=pmax;
this.bits = new BitSet(n);
}
private int generateBits()
{
int k = 0;
for (int i = 0; i < n; ++i)
{
boolean b = bernoulli.getNextBoolean();
this.bits.set(i, b);
if (b) ++k;
}
return k;
}
private int findEvenlySpacedOnes(int k, int[] pos)
{
int[] bitPosition = new int[k];
for (int i = 0, j = 0; i < n; ++i)
{
if (this.bits.get(i))
{
bitPosition[j++] = i;
}
}
int nsteps = n;
boolean found = false;
if (k >= 3)
{
int lastBitSetPosition = bitPosition[k-1];
for (int j1 = 0; !found && j1 < k; ++j1)
{
pos[0] = bitPosition[j1];
for (int j2 = j1+1; !found && j2 < k; ++j2)
{
pos[1] = bitPosition[j2];
++nsteps;
pos[2] = 2*pos[1]-pos[0];
if (pos[2] > lastBitSetPosition)
break;
found = this.bits.get(pos[2]);
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
int k = generateBits();
int[] pos = new int[3];
int nsteps = findEvenlySpacedOnes(k, pos);
return new TestResult(k, nsteps);
}
public static void main(String[] args)
{
int n;
int ntrials;
double pmin = 0, pmax = 1;
try {
n = Integer.parseInt(args[0]);
ntrials = Integer.parseInt(args[1]);
if (args.length >= 3)
pmin = Double.parseDouble(args[2]);
if (args.length >= 4)
pmax = Double.parseDouble(args[3]);
}
catch (Exception e)
{
System.out.println("usage: EvenlySpacedOnesTest N NTRIALS [pmin [pmax]]");
System.exit(0);
return;
}
final StatisticalSummary[] statistics;
statistics=new StatisticalSummary[n+1];
for (int i = 0; i <= n; ++i)
{
statistics[i] = new StatisticalSummary();
}
EvenlySpacedOnesTest test = new EvenlySpacedOnesTest(n, ntrials, pmin, pmax);
int printInterval=100000;
int nextPrint = printInterval;
for (int i = 0; i < ntrials; ++i)
{
TestResult result = test.run();
statistics[result.k].add(result.nsteps);
if (i == nextPrint)
{
System.err.println(i);
nextPrint += printInterval;
}
}
StatisticalSummary.printOut(System.out, statistics);
}
}