On Wednesday 12 of October 2005 13:04, Kameník Jaroslav wrote: > No to je pomerne jasny.. > > Naplneni ArrayListu od zacatku bude mit > slozitost O(n^2) - N x vkladam a N x kopiruju pole > (celkova velikost zkopirovanych dat = suma od 0 do N-1) > > U LinkedListu je to O(n) - N x naalokuju objekt a nastavim pointery. > > Pokud to plnite na konci, LinkedList vychazi stejne, ArrayList > bude mit O(n) (vkladam N x, log(N) x se realokuje pole, ale > amortizovana slozitost na jedno vkladani vyjde konstatni..) > > Takze rozdil v rychlosti bude v tomto pripade konstanta zpusobena > tim, ze alokace malych objektu nic nestoji, jak pravi O SUN :)
Diky za rozbor. Z nej plyne, ze nejvyhodnejsi pouziti LinkedListu je na implementaci vlastniho zasobniku. ;-) K tomu ale uz mame Stack ;-) Ale ted vazne. Bohuzel se rozbor nezaklada na vlastni implementaci LinkedListu, u ktereho je diky oboustrannosti skok na posledni prvek o jeden hop pomalejsi nez skok na prvni prvek, protoze tyto dva prvky jsou navzajem provazane. Proto je fronta pomoci LinkedListu vyrazne rychlejsi nez u ArrayListu, protoze pridani (i odebrani) pres hlavu i za ocas je stejne rychle a nic se nemusi prochazet, natoz kopirovat. Nevic vyhledavani podle indexu se diky teto vlastnosti muze vyuzit puleni intervalu, tudiz stredni doba vyhledani klesa na polovinu. -- Oto 'tapik' Buchta, [EMAIL PROTECTED] Senior Engineer, Systinet Corp, http://www.systinet.com
