Проксмап сортирање — разлика између измена
Садржај обрисан Садржај додат
Нема описа измене |
м razne izmene |
||
Ред 126:
=== Перформансе ===
Временска сложеност рачунања H, P и L је O(n). Сваки се рачуна током једног проласка кроз низ, уз константно проведено време у свакој локацији низа.
* Најгори случај: MapKey складишти све елементе у један подниз, што доводи до стандардног сортирања уметањем
* Најбољи случај: MapKey складишти мали број елемената у сваки подниз у редоследу где долази до најбољег случаја сортирања уметањем. Свако сортирање уметањем је сложености O(c), ''c'' је величина подниза; постоји ''p'' поднизова, стога '''p * c = n''', тако да фаза уметања сложености O(n); стога сложеност ProxmapSort-а је O(n).
* Просечан случај: Највећа величина сваког подниза је ''c'', константа; уметање за сваки подстринг је онда у најгорем случају O(c^2) сложености, такође константа. (Стварно време заправо може бити много боље, пошто c елемената није сортирано док се последњи елемент не дода у кофу). Укупно време представља број кофа, '''(n/c)''', сложености O(c^2)=O(n).
| |||