Average case of simple algorithm like binary search
-
05-11-2019 - |
题
These questions is about one of my research. As I am not a computer scientist, formal answering is difficult to me.
I have a special search algorithm which the explanation here will take a lot of time. However I can explain it shortly by some notations.
Assume that we have an array of somethings (in my real research they are some cities which they form a path graph) with length $n$. First, we should select one element by some rules( I ignore the rules here) with $O(1)$ time. indeed, according to the rules this element is nearer element to my solution. However, as this rule does not follow a particular order, we can assume that the selection is random.
This element may take tree label, say $L$, $R$ and $M$. The label can be found in $O(1)$ time. If the label is $M$, then we found the solution. Else, if the label is $l$, then we found that this element is not solution and also all elements before it can not be a solution. similarly, this scenario is also correct when the label is $R$, i.e. this element is not solution and also all elements after it can not be a solution. This leads a binary like search algorithm with the difference that the first element is not the median of array. we can summarize the above statements as the following algorithm.
Input: An array $A$ with length $n$.
while length(A) > 1 do
1. choose an element $k$ (for example, randomly with uniform
distribution) with $O(1)$. Find its label with $O(1)$.
2.If the label is $M$, then stop
3. else if the label is $l$ then delete $k$ and all elements before $k$.
4. else if the label is $r$ then delete $k$ and all elements after $k$.
end while
I know that the worst case complexity is $O(n^2)$ and the best complexity is $O(1)$. What is the average complexity?
没有正确的解决方案