|
|
Grafy a tabuľky |
| Sekvenčné vyhľadávanie s podmienkou
|
Priemerné počty porovnaní vybraných implementácií |
//sekvencne vyhladavanie zadaneho prvku "hladany" s podmienkou
//pole musi byt usporiadane vzostupne (na zaciatku pola je prvok s najmensou hodnotou)
//funkcia vracia index zadaneho prvku v poli (v pripade neuspechu vyhladavania vracia -1)
template < class T, int velkost_ >
int CPole < T, velkost_ > ::najdi_sekv_int_podm(T hladany){
int index=0;
while (++p_a_porovnani_ && index < velkost_) {
if (++p_b_porovnani_ && pole_[index] < hladany) {++p_a_cyklov_; index++;}
else {
if (++p_b_porovnani_ && pole_[index]==hladany) return index;
else return -1;
}
}
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 |
6,500 |
4,500 |
0,0864 |
| 100 |
50,50 |
51,50 |
49,50 |
0,4310 |
| 1.000 |
500,5 |
501,5 |
499,5 |
3,885 |
| 10.000 |
5000,5 |
5001,5 |
4999,5 |
38,20 |
| 100.000 |
50000,5 |
50001,5 |
49999,5 |
425,5 |
|
Počet cyklov pri úspešnom vyhľadávaní uvedeného algoritmu je približne n/2. Keďže počas každého cyklu vykoná 2 porovnania, je počet všetkých porovnaní približne 2*(n/2). |
| |
| 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 |
5,100 |
5,900 |
4,100 |
0,0929 |
| 100 |
51,05 |
52,05 |
50,05 |
0,4410 |
| 1.000 |
500,1 |
501,1 |
499,1 |
3,875 |
| 10.000 |
4962,8 |
4963,8 |
4961,8 |
38,10 |
| 100.000 |
49854,0 |
49855,0 |
49853,0 |
421,5 |
|
Počet cyklov pri neúspešnom vyhľadávaní je približne rovnaký ako pri úspešnom vyhľadávaní, teda rádovo n/2. Je to preto, lebo ak algoritmus nenájde prvok na predpokladanom mieste v zoradenom poli a teda nájde číslo väčšie ako hľadané, nepokračuje ďalej vo vyhľadávaní, ale skončí. Keďže v každom cykle vykoná 2 porovnania, je počet porovnaní približne n. |
| |
| |
Závislost dĺžky času trvania algoritmu od veľkosti vstupného pola |
Časová zložitosť tohto algoritmu je podobne ako pri algoritmoch pre neusporiadané polia lineárna. Môžeme si však všimnúť, že aj pre úspešné a aj pre neúspešné vyhľadávanie sú časy trvania algoritmu takmer totožné. |
 |
| |
10 |
100 |
1.000 |
10.000 |
100.000 |
| úspešné vyhľadávanie |
0,0864 |
0,4310 |
3,890 |
38,20 |
426,0 |
| neúspešné vyhľadávanie s p=0,9 |
0,0929 |
0,4410 |
3,880 |
38,10 |
422,0 |
|
| |
| |
Porovnanie algoritmu s predchádzajúcimi algoritmami |
Sekvenčný algoritmus s podmienkou nepriniesol aj napriek usporiadanému vstupnému poľu žiadne veľké zrýchlenie. Pri úspešnom vyhľadávaní nie je ani tak rýchly ako sekvenčné vyhľadávanie so zarážkou. Má však jednu výhodu a tou sú takmer rovnaké časové nároky na úspešné a aj neúspešné vyhľadávanie, čo o ďalších dvoch algoritmoch neplatí. |
 |
| |
10 |
100 |
1.000 |
10.000 |
100.000 |
| úspešné sekvenčné |
0,0809 |
0,4290 |
3,910 |
38,10 |
422,0 |
| neúspešné sekvenčné s p=0,9 |
0,1203 |
0,7900 |
7,310 |
72,80 |
962,0 |
| úspešné sekvenčné so zarážkou |
0,0905 |
0,4040 |
3,580 |
34,90 |
386,0 |
| neúspešné sekvenčné so zarážkou s p=0,9 |
0,1283 |
0,7280 |
6,720 |
66,10 |
915,0 |
| sekvenčné s podmienkou |
0,0929 |
0,4410 |
3,880 |
38,10 |
422,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. |
