Shell sort: differenze tra le versioni
Contenuto cancellato Contenuto aggiunto
+aggiunto portale |
→Analisi: aggiunta di una sequenza h adoperabile dello shellsort per avere un costo computazionale n alla 4/3 |
||
Riga 64:
([[Donald Knuth|Knuth]]) Con la sequenza ''h'' 1, 4, 13, 40, 121, ..., 3''h''<sub>''s''-1</sub> + 1 = (3<sup>''s''</sup> - 1)/2, ... Shellsort esegue O(''n''<sup>3/2</sup>) passi per ordinare una sequenza di lunghezza ''n''.
(sequenza non definita) con la sequenza h 1, 8, 23, ..., 4i+1 + 3*2i +1, ... Shellsort esegue O (''n''<sup>4/3</sup>) passi per ordinare una sequenza di lunghezza n.
([[Robert Sedgewick|Sedgewick]]) Con la sequenza ''h'' 1, 5, 19, 41, 109, 209, ... (descritta qui sotto), Shellsort esegue O(''n''<sup>4/3</sup>) passi per ordinare una sequenza di lunghezza ''n''.
| |||