Tempo minimo per la matrice di ordinamento parziale?

Question

Ci viene data una matrice parzialmente ordinato A, cioè for i=1, 2, ..., n-k abbiamo:

A[i]<= A[i+k] 

Per classificare completamente matrice, dobbiamo almeno O(n log k) tempo.

qual è la condizione e la soluzione che rendono questo assioma vero sempre?

Answer 1

È possibile utilizzare l'ordinamento di shell da questo problema. In questo algoritmo, dopo ogni fase e qualche incremento hk, per ogni i, abbiamo un [i] ≤ a [i + hk]. tutti gli elementi distanziati sono separati. Si dice che questo array sia hk - ordinato. l'output di shell sort è 1-ordinato. se l'array è k-ordinato, quindi l'ordinamento di shell ha bisogno di O (log k) per l'array di ordinamento completamente. ogni fase ha bisogno di O (n) quindi l'ordine totale è O (n log k).

supponga di voler ordinare questa matrice:

questa matrice è 4-ordinato (k = 4). per ordinare questo, è necessario 2 fasi (h2 = 2, h3 = 1) Quindi sono necessarie due fasi (lg 4 o lg k). Ad ogni fase, ci sono sotto-array n/k che devono essere ordinati. ogni ordinamento sub-array con ordinamento per inserimento. Ordine di ordinamento ogni sottoarray è O (n). Infine, ordine totale O (n * lg k) = O (n log k).