|
|
Grafy a tabuľky |
| Vyhľadávanie extrému v strome
|
Priemerné počty porovnaní vybraných implementácií |
//vyhladavanie minimalnej hodnoty v strome urcenom uzlom "uzol" pomocou cyklu while
//funkcia vracia ukazovatel na uzol s minimalnou hodnotou
CUzol* CStrom::najdi_cykl_min_uzol(CUzol* uzol){
if (++p_a_porovnani_ && uzol)
while (++p_a_porovnani_ && uzol->lavy()) {++p_a_cyklov_; uzol=uzol->lavy();}
return uzol;
} |
| Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie. |
| počet uzlov v strome |
p_a_porovnani_ |
p_a_cyklov_ |
čas |
| 15 |
5,000 |
3,000 |
0,3124 |
| 127 |
8,000 |
6,000 |
0,5528 |
| 1.023 |
11,00 |
9,000 |
0,8289 |
| 8.191 |
14,00 |
12,00 |
1,048 |
| 65.535 |
17,00 |
15,00 |
1,348 |
|
Počet cyklov závisí v tomto prípade iba od toho, v akej hĺbke sa nachádza hľadaná hodnota. Pre strom s n uzlami je to práve (log(2) n). Tento algoritmus však vždy robí o jeden cyklus menej. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Závislosť dĺžky trvania tohto algoritmu je od počtu uzlov v strome logaritmická. |
 |
| |
15 |
127 |
1.023 |
8.191 |
65.535 |
| hľadanie minima |
0,3124 |
0,5528 |
0,8289 |
1,048 |
1,348 |
|
| |
| |
| Poznámka: Algoritmy boli testované na počítači s procesorom AMD Athlon(tm) XP 1700+ a s 256 MB operačnou pamäťou pod operačným systémom Windows XP. Všetky časy uvedené v tabuľke sú v mikrosekundách. |
