随机二元搜索的运行时间 [英] Running Time of Randomized Binary Search

问题描述

考虑以下二进制搜索的愚蠢随机变量。给您一个排序数组
A，它包含n个整数，并且要搜索的整数v是从A中随机选择的。
然后，而不是将v与数组中间的值进行比较，则随机二分查找
变体从1到n中选择一个随机数r，并将v与A [r]进行比较。根据
v是大还是小，此过程在左子数组或右子数组
上递归重复，直到找到v的位置。证明该算法的预期运行时间有一个严格的界限。

这就是我得到的T（n）

T（n）= T（nr）+ T（r）+Θ（1）

解决方案

您对T（n）的公式并不完全正确。实际上，

让我们尝试研究所有情况。当我们通过在任意随机点上划分数组来减少问题的大小时，减少的子问题将具有从1到n的任何大小，而且概率是均匀的。因此，以概率1 / n，搜索空间变为r。因此，预期的运行时间变为

T（n）= sum（T（r）* Pr（搜索空间变为r））+ O（1 ）=总和（T（r））/ n + O（1）

哪个给出，

T（n）=平均值（T（r））+ O（1）

让随机二进制排序的预期时间复杂度为T（n）。

  T（n）= [T（1）+ T（2）+ ... + T（n）] / n + 1 
n * T（n）= T（1）+ T（2）+ ... + T（n）+ n 
（n-1）* T（n-1）= T（1）+ T（2）+ ... + T（n-1）+ n-1 [用n-1替换n] 
n * T（n）-（n-1）* T（ n-1）= T（n）+ 1 
（n-1）* T（n）-（n-1）* T（n-1）= 1 
（n-1）* T（n）=（n-1）* T（n-1）+ 1 
 T（n）= 1 /（n-1）+ T（n-1）
 T（n） = 1 /（n-1）+ 1 /（n-2）+ T（n-2）[T（n-1）= T（n-2）+ 1 /（n-2）] 
 ... 
 T（n）= 1 + 1/2 + 1/3 + ... + 1 /（n-1）= H（n-1）< H（n）= O（log n）
 [H（n）=前n个自然数的倒数和] 
  

因此， T（n）= O（log n）

谐波编号

边界H（n）

Consider the following silly randomized variant of binary search. You are given a sorted array A of n integers and the integer v that you are searching for is chosen uniformly at random from A. Then, instead of comparing v with the value in the middle of the array, the randomized binary search variant chooses a random number r from 1 to n and it compares v with A[r]. Depending on whether v is larger or smaller, this process is repeated recursively on the left sub-array or the right sub-array, until the location of v is found. Prove a tight bound on the expected running time of this algorithm.

Here is what I got for the T(n)

T(n) = T(n-r) + T(r) + Θ(1)

However, I have no clue how to get a tight bound.

解决方案

Your formulation of T(n) is not completely correct. Actually,

Lets try to look over all the cases. When we reduce the problem size by partitioning the array across any random point, the reduced sub-problem will have any size from 1 to n with uniform probability. Hence with probability 1/n, search space becomes r. So expected running time becomes

T(n) = sum ( T(r)*Pr(search space becomes r) ) + O(1) = sum ( T(r) )/n + O(1)

Which gives,

T(n) = average(T(r)) + O(1)

Let expected time complexity of random binary sort be T(n).

T(n) = [ T(1)+T(2)+...+T(n)]/n + 1
n*T(n) = T(1)+T(2)+...+T(n) + n
(n-1)*T(n-1) = T(1)+T(2)+...+T(n-1) + n-1       [substituiting n by n-1]
n*T(n) - (n-1)*T(n-1) = T(n) + 1
(n-1)*T(n) - (n-1)*T(n-1) =  1
(n-1)*T(n) = (n-1)*T(n-1) + 1
T(n) = 1/(n-1) + T(n-1)
T(n) = 1/(n-1) + 1/(n-2) + T(n-2)               [ T(n-1) = T(n-2) + 1/(n-2) ]
...
T(n) = 1 + 1/2 + 1/3 + ... + 1/(n-1) = H(n-1) < H(n) = O(log n) 
[ H(n) = reciprocal sum of first n natural numbers   ]

so, T(n) = O(log n)

Harmonic number

bound of H(n)

这篇关于随机二元搜索的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！