Pergunta

Consider two algorithms; we analysis their run time only by counting the number of comparisons

TwoMax1(A):   
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > L:
             S = L
             L = A[i]
         else
            if A[i] > S
                S = A[i]
    return (L,S)



 TwoMax2(A):   
     S = negative infinite
     L = negative infinite
     loop through the array A
         if A[i] > S:
            if A[i] > L:
             S = L
             L = A[i]
            else
                S = A[i]
    return (L,S)

Here is my approach for the first algorithm:

(1) define our sample space. Since the returned output is a pair, maximum and second maximum could be anywhere in the array. For each maximum, there are $(n-1)$ possible index for second maximum, and we have $n$ possible index for the maximum value; So sample space: $S = \{(A[0],A[1]),(A[0], A[2]),(A[0],A[3]),\dots\}$ and so on.

Define an indicator $I_i = 1$ iff $A[i] > \max \{A[0], A[1], \dots, A[i-1]\}$.

The total expected comparison of comparing to maximum would be $$\mathbb{E} (\sum_{i=0}^n I_i) = \sum_{i=0}^n \mathbb{E}(I_i) = \mathrm{Prob}(A[i] > \max \{A[0], A[1],\dots, A[i-1]\}) = \frac{n+1}{2}.$$

where $$\mathrm{Prob}(A[i] > \max \{A[0], A[1], \dots, A[i-1]\}) = \frac{i}{n}$$ because under the sorted array, we have $\frac{i}{n}$ chance of choosing a integer that greater than $A[0], A[1],\dots,A[i-1]$.

Now similar, the total expected comparison of comparing to second maximum would be same; and we sum two parts together up is $n+1$.

Is this a good way of approaching? If so, I also want to know some other ways of doing it, for example, define a different random variable to solve the second function.

Nenhuma solução correta

Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange
scroll top