ISSN:
1432-0541
Schlagwort(e):
Shellsort
;
Sorting
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Informatik
,
Mathematik
Notizen:
Abstract We consider the worst-case running time of Shellsort when only a constant number,c, of increments are allowed. Forc=3, we show that Shellsort can be implemented to run inO(N 5/3) time, which is optimal. Forc=4, we further improve the running time toO(N 11/7), and, forc=5, we obtain a bound ofO(N 23/15). We also show anO(N 1+1/k ) bound for generalc, wherek=[(1+√8c+1)/4]. Forc=6, this isO(N 3/2).
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1007/BF01944355
Permalink