Milyen futásideje/komplexitása van az alábbi algoritmusnak?

Attól is függ milyen rendezési algoritmust használsz:

[link]

Rendezést N*logN idővel fogod tudni.

Tegyük fel, hogy a string-ek legrosszabb esetben M hosszúak és N darab van belőle. Ekkor N*M*logM

Most pedig a rendezett stringeket rendezzük a tömbben:

N*logN

Az eredmény a kettő egymásutáni futtatása, tehát

N*M*logM + N*logN, felsőhatárral, jó algoritmussal.

Quick sort komplexitása csak rossz pivot választással (és rendezett tömbre hívva) négyzetes, a Java implementáció nyilván nem ilyen.

Illetve nyilvánvalóan nem lehet egyváltozós komplexitása az algoritmusnak.

#4-es egész jó úton jár, de nem veszi figyelembe, hogy két String összehasonlítása nem O(1)-es művelet (mivel stringeket karakterenként hasonlítunk össze, nem mindegy, hogy 3 karakterből állnak, vagy 3 millióból).

Legyen a leghosszabb String s és a tömb mérete n.

Egy String rendezése s*log s.

n String rendezése n*s*log s.

Ezután rendezhetjük a tömböt, ha a Stringek egy karakterből állnának, akkor ez n*log n lenne, de bejön egy s szorzó, tehát s*n*log n lesz.

Tehát a vége n*s*log s + n*s*log n, azaz O(n*s*(log s + log n)) a komplexitás.

+1 az utolsónak

[link]

Egy kis megjegyzés az előbbiekhez: Javaban az Arrays.Sort(Object[]) TimSortot használ nem QuickSortot. Tehát referencia típusokoknál TimSort. Viszont az érték típusokat már Dual-Pivot QuickSorttal rendez.

TimSort: [link]

D-QuickSort

[link]