diff options
fix pract04 readme
1 files changed, 0 insertions, 15 deletions
| -rw-r--r-- | Practicum/pract04/readme.md | 15 |
diff --git a/Practicum/pract04/readme.md b/Practicum/pract04/readme.md index 2c62cff..351b8a8 100644 --- a/Practicum/pract04/readme.md +++ b/Practicum/pract04/readme.md @@ -110,21 +110,6 @@ $$ Получихме, че алгоритъмът има сложност O(logn) в `worst-case`. -Нека в `average-case` сме направили k стъпки. На всяка една от стъпките n ще се променя както следва: - -- Първа итерация: $n$ -- Втора итерация: $\frac{n}{2}$ -- Трета итерация: $\frac{n}{4}$ -- -... -- k-та итерация: $\frac{n}{2^{k-1}}$ - -Съответно намираме сложността чрез уравнението: - -$$ -\frac{n}{2^k} = t \implies \frac{n}{t} = 2^k \implies k = \log_2 \frac{n}{t} \implies ≈\Theta(\log n) -$$ - `Best-case` ще имаме, когато елементът, който търсим, е точно в средата. Съответно сложността ни тогава е константна (O(1)) - няма да разглеждаме други интервали. ## Стандартни алгоритми за търсене - `std::find`, `std::find_if` и `std::find_if_not` |