Intuição do limite inferior para encontrar o mínimo de $ N $ (distintos) elementos é $ n-1 $ como tratado em clrs

Question

Eu estava passando pela introdução de texto para algoritmos por Cormen ET. al. Onde houve uma discussão sobre o fato de que encontrar o mínimo de um conjunto de elementos $ n $ (distinto) elementos com $ n -1 $ comparações é ideal como não podemos fazer melhor do que isso, o que significa que precisamos mostrar que o tempo de execução do algoritmo que encontra o mínimo de um conjunto de $ n $ elementos é $ \ ômega (n) $ .

É isso que o texto diz para justificar o limite inferior.

.

Podemos obter um limite inferior da $ n - 1 $ comparações para o problema de determinar o mínimo. Pense em qualquer algoritmo que determina o mínimo como um torneio entre os elementos. Cada comparação é uma partida no torneio em que o menor dos dois elementos vence. Observando que todo elemento, exceto que o vencedor deve perder pelo menos uma partida, concluímos que $ N-1 $ comparações são necessárias para determinar o mínimo.

Agora eu poderia fazer a coisa da minha própria maneira como:

O que eu fiz é uma comparação de cima para baixo, mas os autores por suas palavras "observando que cada elemento, exceto o vencedor, deve perder pelo menos uma partida, concluímos que $ n-1 $ comparações são necessárias para determinar o mínimo. " Parece que eles estão apontando para uma abordagem de baixo para cima que infelizmente não posso fazer.

Como,

"que cada elemento, exceto que o vencedor deve perder pelo menos um jogo" $ \ implica $ " $ N-1 $ comparações são necessárias para determinar o mínimo ".

Answer 1

Cada partida tem exatamente um vencedor e um perdedor. Se cada elemento, exceto que o vencedor deve perder pelo menos uma partida, deve haver pelo menos $ n-1 $ corresponde, como caso contrário, haveria uma partida com dois perdedores. Então, pelo menos $ n-1 $ correspondências são nessecary para determinar um vencedor, ou seja, $ N-1 $ comparações são nessecary para determinar o mínimo.

---

.

A explicação dada no livro é válida, mas eu pessoalmente prefiro outra abordagem. (O que requer alguma teoria do gráfico elementar) Suponha que você desenhe o gráfico com os elementos como nós e desenham uma borda para cada par de elementos que seu algoritmo compara. Note que é impossível saber qual de um par de elementos é menor se não houver caminho entre eles neste gráfico. Então, se determinamos o mínimo, este gráfico deve ser conectado. Qualquer gráfico conectado em $ n $ nós tem pelo menos $ N-1 $ bordas, então deve ter foi $ n-1 $ comparações.