Grafy a tabuľky

Vyhľadávanie v obojsmerne zreťazenom zozname podľa aktuálnej pozície

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

//sekvencne vyhladavanie zadanej hodnoty "hladany" 
//v OZ zozname od zaznamu "aktualny" s podmienkou
//zoznam musi byt vzostupne usporiadany 
//(na zaciatku zoznamu je zaznam s najmensou hodnotou)
//zoznam musi byt zretazeny dokola
//funkcia vracia ukazovatel na najdeny zaznam (v pripade neuspechu vyhladavania vracia 0 
CZaznam_OZ* CZoznam_OZ::najdi_sekv2_zaznam_podm(int hladany, CZaznam_OZ* aktualny){
	if (++p_a_porovnani_ && !aktualny) return 0;
	if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;

	CZaznam_OZ* prvy=aktualny;
	if (++p_b_porovnani_ && hladany < aktualny->hodnota()) {
		do {
			aktualny=aktualny->predch();
			++p_posunuti_;
		} while (++p_b_porovnani_ && hladany < aktualny->hodnota() &&
			++p_c_porovnani_ && aktualny!=prvy);
	if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;
	else return 0;
	}
	else {
		do {
			aktualny=aktualny->dalsi();
			++p_posunuti_;
		} while (++p_b_porovnani_ && hladany > aktualny->hodnota() &&
			++p_c_porovnani_ && aktualny!=prvy);
	if (++p_b_porovnani_ && hladany==aktualny->hodnota()) return aktualny;
	else 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_c_porovnani_ p_posunuti_ čas
10 1,000 4,300 1,200 1,900 0,4653
100 1,000 38,52 34,52 35,52 2,913
1.000 1,000 331,3 327,3 328,3 26,96
10.000 1,000 3343,8 3339,8 3340,8 269,3
Z tabuľky môžeme vyčítať, že priemerný počet cyklov pri tomto type vyhľadávania je približne n/3. Počet porovnaní je približne 2*n/3.
 
 

Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola

Závislosť dĺžky trvania tohto algoritmu od veľkosti zoznamu je lineárna. Podobné časy by vyšli aj pre zväčša neúspešné vyhľadávanie (tak ako tomu bolo pri sekvenčnom vyhľadávaní s podmienkou v poliach), pretože ak by algoritmus nenašiel hľadanú hodnotu na predpokladanom mieste, ďalej by už nehľadal a teda by mal veľmi podobný počet posunutí v zozname ako úspešné vyhľadávanie.
  10 100 1.000 10.000
úspešné vyhľadávanie 0,4653 2,913 26,96 269,3
 
 

Porovnanie algoritmu s predchádzajúcimi algoritmami

Ako môžeme vidieť, ak začneme vyhľadávať od začiatku zoznamu, vyhľadávanie trvá v priemernom prípade dlhšie ako keď začneme od aktuálnej pozície. Z toho pohľadu by bolo azda najefektívnejšie vždy vyhľadávať od stredu zoznamu. Tento stred by však bolo nutné niekde uchovávať a pri vkladaní alebo vynímaní záznamov zo zoznamu ho aj meniť. Existujú zoznamy, ktoré si uchovávajú ukazovatele aj do stredu zoznamu a tiež ukazovatele na niektoré iné dôležité pozície, tými sa však nebudeme na týchto stránkach zaoberať.
  10 100 1.000 10.000
úspešné vyhľadávanie od aktuálnej pozície 0,4653 2,913 26,96 269,3
vyhľadávanie od zažiatku zoznamu úspešné 0,5414 4,230 40,52 406,5
vyhľadávanie od zažiatku zoznamu neúspešne s p=0,9 0,5074 4,520 40,57 404,5
 
 
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.