Здесь нет теоретического ответа, но я написал быструю Java-программу для изучения поведения во время выполнения как функции k и n, где n - общая длина бита, а k - число единиц. Я с несколькими из ответчиков, которые говорят, что «обычный» алгоритм, который проверяет все пары позиций битов и ищет 3-й бит, хотя для этого потребуется O (k ^ 2) в худшем случае, в реальность, потому что в худшем случае нужны разреженные цепочки битов, это O (n ln n).
В любом случае, вот программа ниже. Это программа в стиле Монте-Карло, которая запускает большое количество испытаний NTRIALS для константы n и случайным образом генерирует наборы битов для диапазона значений k, используя процессы Бернулли с ограничениями плотности единиц, которые могут быть заданы, и записывает время выполнения. найти или не найти триплет из равномерно распределенных, время измеряется в шагах, а не во времени ЦП. Я запустил его для n = 64, 256, 1024, 4096, 16384 * (все еще выполняется), сначала тестовый запуск с 500000 испытаний, чтобы увидеть, какие значения k занимают самое продолжительное время работы, затем другой тест с 5000000 испытаниями с суженными сосредоточиться на плотности, чтобы увидеть, как эти значения выглядят. Самое длинное время работы происходит при очень разреженной плотности (например, для n = 4096 пики времени работы находятся в диапазоне k = 16-64, с небольшим пиком для среднего времени работы при 4212 шагах при k = 31, максимальное время работы достигло максимума при 5101 шаги @ k = 58). Похоже, что для шага O (k ^ 2) в худшем случае потребовалось бы чрезвычайно большое значение N, чтобы стать больше шага O (n), когда вы сканируете цепочку битов, чтобы найти индексы позиции 1.
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);
// this algorithm for mean,std dev based on Knuth TAOCP vol 2
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; }
// some may quibble and use n-1 for sample std dev vs population std dev
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 // see http://en.wikipedia.org/wiki/Bernoulli_process
{
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);
}
/*
* generate random bit string
*/
private int generateBits()
{
int k = 0; // # of 1's
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; // first, it takes N operations to find the bit positions.
boolean found = false;
if (k >= 3) // don't bother doing anything if there are less than 3 ones. :(
{
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];
// calculate 3rd bit index that might be set;
// the other two indices point to bits that are set
if (pos[2] > lastBitSetPosition)
break;
// loop inner loop until we go out of bounds
found = this.bits.get(pos[2]);
// we're done if we find a third 1!
}
}
}
if (!found)
pos[0]=-1;
return nsteps;
}
/*
* run an algorithm that finds evenly spaced ones and returns # of steps.
*/
public TestResult run()
{
bernoulli.setProbability(pmin + (pmax-pmin)*random.nextDouble());
// probability of bernoulli process is randomly distributed between pmin and pmax
// generate bit string.
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; // make the compiler happy
}
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);
}
}