Grafy a tabuľky

Sekvenčné vyhľadávanie

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

 
//sekvencne vyhladavanie zadaneho prvku "hladany"
//funkcia vracia index zadaneho prvku v poli (v pripade neuspechu vyhladavania vracia -1) 
template < class T, int velkost_ > 
int CPole < T, velkost_ > ::najdi_sekv_index(T hladany){
	int index=0;
	while (++p_a_porovnani_ && index < velkost_) {
		++p_a_cyklov_;
		if (++p_b_porovnani_ && pole_[index]==hladany) return index;
		else index++;
	}
	return -1;
}
Počet porovnaní, cyklov a času trvania algoritmu pre úspešné vyhľadávanie.
počet prvkov v poli p_a_porovnani_ p_b_porovnani_ p_a_cyklov_ čas
10 5,500 5,500 5,500 0,0809
100 50,50 50,50 50,50 0,4290
1.000 500,5 500,5 500,5 3,905
10.000 5000,5 5000,5 5000,5 38,10
100.000 50000,5 50000,5 50000,5 421,6
Z predchádzajúcej tabuľky je vidieť, že počet porovnaní pri priemernom úspešnom vyhľadávaní je rádovo 2*(n/2). Je to preto, lebo v priemernom prípade pri úspešnom vyhľadávaní je prvok nájdení približne uprostred poľa. Počet cyklov algoritmu je približne n/2 a v každom cykle urobí algoritmus 2 porovnania.
 
Počet porovnaní, cyklov a času trvania algoritmu pre neúspešné vyhľadávanie s p=0,9.
počet prvkov v poli p_a_porovnani_ p_b_porovnani_ p_a_cyklov_ čas
10 9,300 8,500 8,500 0,1203
100 98,08 97,12 97,12 0,7897
1.000 950,1 949,2 949,2 7,310
10.000 9543,4 9542,5 9542,5 72,80
100.000 97727,2 97726,2 97726,2 961,9
Pre zväčša neúspešné vyhľadávanie je počet porovnaní rádovo 2*n. Algoritmus musí totiž prejsť celé pole, aby zistil, že sa prvok v poli nenachádza. Preto je počet cyklov len o málo menší ako n. V každom cykle urobí algoritmus 2 porovnania.
 
 

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola
Tento algoritmus má lineárnu časovú závislosť dĺžky trvania od veľkosti vstupného poľa. Pre 10-násobné zväčšenie vstupného poľa je aj čas potrebný na ukončenie algoritmu približne 10-násobne väčší. Pre malé polia je potrebný čas ovplyvňovaný samotným volaním funkcie. Pre väčšie polia môže byť čas ovplyvňovaný vymieňaním stránok v operačnej pamäti operačným systémom počítača.
  10 100 1.000 10.000 100.000
úspešné vyhľadávanie 0,0809 0,4290 3,910 38,10 422,0
neúspešné vyhľadávanie s p=0,9 0,1203 0,7900 7,310 72,80 962,0
 
 
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.