时间戳

首页 > 解决方案 > 快速选择的运行时间如何得出，CN = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k))？

arrays - 快速选择的运行时间如何得出，CN = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k))？

问题描述

从未排序的数组中选择第 k 个最大元素时，运行时间为 CN = 2 N + 2 k ln (N / k) + 2 (N – k) ln (N / (N – k)) (介词取自 Robert Sedgewick 教授的 ALgorithms1）。该实现是一个随机的快速选择。

public static Comparable select(Comparable[] a, int k)
{
  StdRandom.shuffle(a);
  int lo = 0, hi = a.length - 1;
  while (hi > lo)
  {
    int j = partition(a, lo, hi);
    if (j < k) lo = j + 1;
    else if (j > k) hi = j - 1;
    else return a[k];
  }
  return a[k];
}

分区子例程是快速排序分区实现，其中 lo 元素用作分区的枢轴。如下图

private static int partition(Comparable[] a, int lo, int hi)
{
  int i = lo, j = hi+1;
  while (true)
  {
    while (less(a[++i], a[lo]))
      if (i == hi) break;
    while (less(a[lo], a[--j]))
      if (j == lo) break;
    if (i >= j) break;
      exch(a, i, j);
  }
  exch(a, lo, j);
  return j;
}

我看到分区的运行时间是（N+1），并且推测分布被打乱，每次运行都会将数组减少到一半，重复出现是（N+N/2+N/4..）所以可以假设 O(N) 时间。这是一个非常乐观的情况。

分布更有可能被分成两半，例如 (C0,Cn-1) 或 (c1, cn-2).. 每个概率为 1/n 倍。现在可以根据上述拆分左侧或右侧中的任何一个的 k 来选择。（如果出现第一种情况，则为 c0 或 cn-1，概率为 1/2N）。现在 cn 将被更改为新的长度，并且将重复相同的步骤直到 j==k。

有人可以帮助推导递归关系及其运行的极限，并最终得出上述 Cn 方程。

注意：-我在 SO 上看到其他人的答案，但他们认为分裂成两半的美好前景，这不太可能发生。像这样一个Quickselect 的平均运行时间

标签： arraysalgorithmmathbig-o

解决方案

推荐阅读