Implementazioni di algoritmi/Shell sort: differenze tra le versioni

Contenuto cancellato Contenuto aggiunto
→‎Analisi: elimina descrizione scorretta della sequenza di fibonacci
Riga 56:
([[Vaughan Pratt|Pratt]])Con la sequenza ''h'' 1, 2, 3, 4, 6, 8, 9, 12, 16, ..., 2<sup>''p''</sup>3<sup>''q''</sup>, ... Shellsort esegue O(''n''·log(''n'')<sup>2</sup>) passi per ordinare una sequenza di lunghezza ''n''.
 
([[Thomas Hibbard|Hibbard]]) Con la sequenza ''h'' 1, 3, 7, 15, 31, 63, 127, ..., 2<sup>''k''</sup> +- 1, ... Shellsort esegue O(''n''<sup>3/2</sup>) passi per ordinare una sequenza di lunghezza ''n''.
 
([[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''.