Grafy a tabuľky

Vyhľadávanie v jednosmerne zreťazenom zozname

Priemerné počty porovnaní vybraných implementácií

 
//sekvencne vyhladavanie zadanej hodnoty "hladany" v JZ zozname od zaznamu "aktualny"
//zoznam musi byt ukonceny nulovym ukazovatelom
//funkcia vracia ukazovatel na najdeny zaznam (v pripade neuspechu vyhladavania vracia 0) 
CZaznam_JZ* CZoznam_JZ::najdi_sekv1_zaznam(int hladany, CZaznam_JZ* aktualny){
	while (++p_a_porovnani_ && aktualny) {
		if (++p_b_porovnani_ && aktualny->hodnota()==hladany) return aktualny;
		else {aktualny=aktualny->dalsi(); ++p_posunuti_;}
	}
	return 0;
}
Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie.
počet záznamov v zozname p_a_porovnani_ p_b_porovnani_ p_posunuti_ čas
10 5,500 5,500 4,500 0,4733
100 50,50 50,50 49,50 4,240
1.000 500,5 500,5 499,5 40,45
10.000 5000,5 5000,5 4999,5 402,5
Priemerný počet posunutí v zozname je približne n/2 a keďže v každom cykle urobí algoritmus dve porovnania, je približný počet porovnaní n.
 
Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s p=0,9.
počet záznamov v zozname p_a_porovnani_ p_b_porovnani_ p_posunuti_ čas
10 9,300 8,500 8,300 0,7327
100 98,08 97,12 97,08 8,030
1.000 950,1 949,2 949,1 76,21
10.000 9543,4 9542,5 9542,4 780,1
Pre zväčša neúspešné vyhľadávanie je priemerný počet posunutí v zozname približne rovný dĺžke zoznamu, vždy však menší. Počet porovnaní je teda približne 2*n.
 
 

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola
Časová zložitosť tohto algoritmu je lineárna, teda pre 10-násobné zväčšenie veľkosti zoznamu, vzrastie aj čas prehľadávania približne 10-násobne. Úspešné vyhľadávanie je rýchlejšie preto, lebo v priemernom prípade stačí prejsť pri takomto vyhľadávaní polovicu zoznamu, zatiaľ čo pri neúspešnom vyhľadávaní treba prejsť celý nezoradený zoznam.
  10 100 1.000 10.000
úspešné vyhľadávanie 0,4733 4,240 40,45 402,5
neúspešné vyhľadávanie s p=0,9 0,7327 8,030 76,21 780,1
 
 
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.