Como a mesclagem de duas matrizes classificadas de n Itens exigem pelo menos 2n - 1 comparações em todos os casos?

Question

A pergunta hw, na página 362 de Estruturas de dados e algoritmos em C ++ : Quarta Editionby Mark Allen Weiss, lê da seguinte forma:

.

Prove que a mesclagem de duas matrizes classificadas de itens n requer pelo menos 2 * N - 1 comparações. Você deve mostrar que, se dois elementos nas listas mescladas forem consecutivas e de diferentes listas, elas devem ser comparadas

Se estamos tentando encontrar o limite inferior, então o número de comparações seria n , não 2 * n - 1? Se o maior elemento for algum array um é menor que o menor elemento em alguma matriz b , então, no máximo, você só teria que fazer n comparações desde depois de todos os Os elementos são colocados na matriz mesclada, então os elementos restantes em B podem simplesmente ser anexado à matriz mesclada.

O limite inferior tem que ser algo que é verdadeiro para cada possível n e toda combinação possível de elementos em ambos os arrays, certo? 2 * n - 1 parece mais como seria o limite superior desde que não há nenhuma maneira de ser mais comparações do que isso.

Nota: Eu não estou pedindo uma resposta para a pergunta do HW como eu sei que é obsoleto. Estou confuso sobre a afirmação implícita A pergunta está fazendo sobre o limite inferior

Answer 1

O que se entende por "limite inferior" neste caso é um limite inferior no número pior caso de comparações.Neste caso, isso também é um limite superior.

.

O limite inferior tem que ser algo que é verdadeiro para cada N e todas as combinações possíveis de elementos em ambos os arrays, certo?2 * n * - 1 parece mais como seria o limite superior, já que não há como haver mais comparações do que isso.

Não, só precisa ser verdade para alguma entrada (para infinitamente muitos n).

Por exemplo, quando dizemos que $ \ ômega (n \ log n) $ é um limite inferior para classificação, isso não significa que cada matriz requer $ \ ômega (n \ log n) $ comparações.Significa apenas que Algumas matrizes exigem que muitas comparações e, portanto, não há $ o (n \ log n) $ -tempo algoritmo paraClassificação.