prednášky Ing. Daniel Hládek PhD.
Ak mám nejaké riešenie:
[note] Podľa https://www.quora.com/What-are-the-most-important-algorithms-used-in-computer-networking/ [/note]
Introduction to Algorithms:
Algoritmus je dobre definovaná postupnosť výpočtov ktorá spracuje jednu alebo viacero hodnôt na výstup.
Ak postup nespĺňa všetky vlastnosti algoritmu, nazývame ho heuristika
vstup => postup = výstup
Pamäťová náročnosť
Časová náročnost (Výpočtová náročnosť)
peňazí = koľko času a koľko prstrojov (pamäte) budeme potrebovať?
Odmeráme spotrebovaný strojový čas a potrebnú pamäť na vzorovom probléme.
Dopredu presne nevieme, koľko dát budeme spracovávať.
Určíme, ktorá inštrukcia má cenu 1.
int vyhladaj(char* pole, int size, char znak){
for (int i = 0; i < size; i++)}
if (pole[i] == znak){
return i;
}
}
return -1;
}V najhoršom prípade:
\(O(n) = O_{prir} + n * (2 * O_{por} + O_{inc})\)
V najlepšom prípade:
\(O(n) = O_{prir} + (2 * O_{por} + O_{inc})\)
V priemernom prípade:
\(O(n) = O_{prir} + 0.5 * n * (2 * O_{por} + O_{inc})\)
Zanedbáme všetky konštanty.
\(C => O(1)\)
\(n C => O(n)\)
\(n^2 C => O(n^2)\)
\(O(n)\)
Predpokladáme, že pole je zotriedené...
int binary_search(int* array,int size,int search){
int first = 0;
int last = size - 1;
int middle = (first+last)/2;
while (first <= last) {
if (array[middle] < search)
first = middle + 1;
else if (array[middle] == search) {
return middle;
}
else{
last = middle - 1;
}
middle = (first + last)/2;
}
return -1;
}v najlepšom prípade
Asymptoticky \(0(1)\)
Zložitosť slučky v najhoršom prípade:
\(O (log_2 (n))\)