Confronto Sort - Teorico

Question

Qualcuno può spiegare la soluzione di questo problema per me?

Si supponga che si è data una sequenza di elementi n per ordinare. La sequenza di ingresso consiste di n = k sottosequenze, ciascuna contenente k elementi. Gli elementi in un determinato sottosequenza sono tutti più piccoli rispetto agli elementi nella sottosequenza successiva e più grande degli elementi della sottosequenza precedente. Così, tutto ciò che è necessario per sorta l'intera sequenza di lunghezza n è quello di ordinare il k elementi in ciascuna delle n = k sottosequenze. Mostra un n lg k limite inferiore per il numero di confronti necessario per risolvere questa variante del problema di smistamento.

Soluzione:

Sia S essere una sequenza di n elementi divisi in n / k sottosequenze ciascuno di lunghezza k dove tutti gli elementi in qualsiasi sottosequenza sono più grandi rispetto a tutti gli elementi di una sottosequenza precedente e più piccolo di tutti gli elementi di un successo sottosequenza.

rivendicazione

Qualunque confronto basato algoritmo di ordinamento per ordinare S deve prendere (n lg k) tempo in caso peggiore.

Prova

Per prima cosa si noti che, come fuori punte nel suggerimento, non possiamo dimostrare la più bassa vincolato moltiplicando insieme i limiti inferiori per l'ordinamento ogni sottosequenza. Questo sarebbe solo dimostrare che non v'è più veloce algoritmo che ordina le sottosequenze indipendentemente. Questo non era quello che ci viene chiesto di dimostrare; Non possiamo introdurre qualsiasi ipotesi extra.

Ora, si consideri la struttura decisionale di altezza h per qualsiasi ordinamento per confronti per S. Dal gli elementi di ogni sottosuccessione possono essere in qualsiasi ordine, una delle caratteristiche k permutazioni corrispondere ordinatamente finale di una sottosequenza. E, dato che ci sono n / k come sottosequenze, ciascuna delle quali può essere in qualsiasi ordine, ci sono (k!) ^ n / k permutazioni di S che potrebbe corrispondere al smistamento di qualche ordine di input. Così, qualsiasi decisione albero per l'ordinamento S deve avere almeno (k!) ^ n / k foglie. Dal momento che un albero binario di altezza h non ha più di 2 ^ h foglie, dobbiamo avere 2 ^ h = (k!) ^ (n / k) o h = lg ((k !) ^ n / k) . Noi quindi avere

     h ≥ lg((k!)^n/k)          -- unbalanced parens - final one added?
       = (n/k) lg(k!)
       ≥ (n/k) lg((k/2)^k/2)
       = (n/2) lg(k/2)

La terza riga viene da k avente k / 2 più termini essendo almeno k / 2 ciascuno. (Assumiamo implicitamente qui che k è ancora. Potremmo regolare con pavimenti e soffitti se k erano dispari.)

Dato che esiste almeno un percorso in qualsiasi albero di decisione per l'ordinamento S che ha una lunghezza almeno (n / 2) lg (k / 2) , il caso peggiore tempo di esecuzione di qualsiasi confronto basato smistamento algoritmo per S è (n lg k) .

Qualcuno mi può camminare attraverso i passaggi nel blocco di codice? Soprattutto il passo quando lg k! diventa lg ((k / 2) ^ k / 2) .

Answer 1

I've reprinted the math below:

(1)      h ≥ lg(k! ^n/k)

(2)      = (n/k) lg(k!)

(3)      ≥ (n/k) lg((k/2)^k/2)

(4)      = (n/2) lg(k/2)

Let's walk through this. Going from line (1) to line (2) uses properties of logarithms. Similarly, going from line (3) to line (4) uses properties of logarithms and the facththat (n / k)(k / 2) = (n / 2). So the trick step is going from line (2) to line (3).

The claim here is the following:

For all k, k! ≥ (k / 2)^{(k / 2)}

Intuitively, the idea is as follows. Consider k! = k(k - 1)(k - 2)...(2)(1). If you'll notice, half of these terms are greater than k / 2 and half of them are smaller. If we drop all the terms that are less than k, we get something (close to) the following:

k! ≥ k(k - 1)(k - 2)...(k / 2)

Now, we have that k / 2 ≥ k, so we have that

k! ≥ k(k - 1)(k - 2)...(k / 2) ≥ (k/2)(k/2)...(k/2)

This is the product of (k / 2) with itself (k / 2) times, so it's equal to (k / 2)^k/2. This math isn't precise because the logic for odd and even values are a bit different, but using essentially this idea you get a sketch of the proof of the earlier result.

To summarize: from (1) to (2) and from (3) to (4) uses properties of logarithms, and from (2) to (3) uses the above result.

Hope this helps!