Перелік хештегів для зручного пошуку постів

📚 Тематика
#php
#architecture
#symfony
#composer
#docker
#sql
#testing
#designpatterns
#solid
#oop
#ddd
#jsonrpc
#microservices
#documentations
#algorithm

🛠 Практика
#examples — корисне
#tools — інструменти, утиліти
#tips — короткі поради
#mistakes — типові граблі
#refactor — приклади рефакторингу
#debug — про дебаг, логування, профілювання
#phpstorm — найкраща IDE
#ai — ШІ помічник

👨‍🏫 Освіта / досвід
#videoarchive — архівне відео з (вебінарів)
#course — матеріали з курсів
#question — питання до аудиторії
#talks — думки й міркування
#4students — для випускників

😄 Гумор і факапи
#game — інтерактивна гра
#rants — бурчання з досвідом
#wtf — код або ситуації, від яких немає слів
#humor — ІТ гумор
#quote — цитати від студентів і колег

Інше
#longread
#holywar
#rating
#career
#work
#series — серія статей

UPD:
В коментарях під цим постом можна писати запити на теми, що вас цікавлять

#course #algorithm #series

🧵На скільки ефективний мій код? 1/8

Складність алгоритму — це один із фундаментальних показників ефективності.

Запускаю серію коротких постів про складність алгоритмів в порядку від найпростішого до найскладнішого.
Кожного дня буду публікувати пост про складність та приклад з кодом, щоб ви це зрозуміли практично.

І почнемо ми з найпростішої, але при цьому дуже важливої складності — O(1), або константної складності.

———

O(1) – Константна складність

Що це означає? Що алгоритм завжди виконується за однакову кількість операцій, незалежно від обсягу даних. Це золото. Це те, що хочеться бачити в критичних місцях: перевірка прав, доступ до кешу, отримання значення з асоціативного масиву.

📌 Приклад: Пошук елемента в хеш-таблиці

$array = ['a' => 1, 'b' => 2, 'c' => 3];
$value = $array['b'];

У цьому прикладі ми одразу знаходимо значення за ключем. Час виконання не залежить від розміру $array — хоч там 3 елементи, хоч 3000. Жодних циклів або рекурсії — це і є O(1).

💡 Цей тип складності зустрічається в PHP та інших технологіях частіше, ніж здається — і чим краще ви його впізнаєте, тим точніше зможете писати оптимальний код. Так, наприклад, працює сховище Redis, Cookie, LocalStorage, кеші фреймворків.

🧠 Завтра поговоримо про O(n) — класичну лінійну складність, яку ви точно вже бачили і робите щодня в кожному циклі.

📎 А поки згадайте інші приклади технологій які використовують цю складність алгоритму, можете поділитися вашими думками в коментарях.

Наступна складність ➡️

#course #algorithm #series

🧵 Наскільки ефективний мій код? 2/8

O(n) – Лінійна складність

Це найпоширеніший тип складності, який ви бачите щодня.

Уявімо, що у вас є масив з 1000 елементів і потрібно знайти одне значення. Якщо масив не відсортований, іншого шляху, окрім як перевірити кожен елемент, просто немає. І саме це означає O(n) — час виконання зростає прямо пропорційно до кількості елементів.

📌 Приклад: Лінійний пошук у масиві

function linearSearch($array, $target) {
    for ($i = 0; $i < count($array); $i++) {
        if ($array[$i] === $target) {
            return $i;
        }
    }
    return -1;
}

Класика. Від foreach, до array_map або array_filter — більшість ваших ітерацій працює саме в O(n).

O(n) — це ще не погано. Це нормально. Але якщо обробляєте мільйони записів — треба думати, як зробити краще.

🧠 Завтра обговоримо O(log n) і двійковий пошук.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵 Наскільки ефективний мій код? 3/8

O(log n) – Логарифмічна складність

Це одна з найефективніших складностей, яку тільки можна досягти в реальних задачах з великим обсягом даних.

📚 Уявімо, що в нас є телефонна книга з 1 000 000 імен, і ми шукаємо конкретне. Лінійно довелося б перевірити кожне імʼя і це зайняло б безліч часу. Але якщо ми будемо розрізати масив навпіл кожного разу, відкидаючи половину, яка нам точно не підходить — отримаємо двійковий пошук, і результат знайдеться за ~20 кроків. Це й є логарифмічна ефективність.

Такий підхід працює лише з відсортованими даними. І саме це лежить в основі багатьох пошукових і оптимізаційних алгоритмів.

📌 Приклад: Двійковий пошук у відсортованому масиві

function binarySearch($array, $target) {
    $left = 0;
    $right = count($array) - 1;

    while ($left <= $right) {
        $middle = floor(($left + $right) / 2);
        if ($array[$middle] === $target) return $middle;

        if ($array[$middle] < $target) {
            $left = $middle + 1;
        } else {
            $right = $middle - 1;
        }
    }
    return -1;
}

🔄 Кожний крок зменшує область пошуку вдвічі. І замість мільйона перевірок — лише кілька десятків. Ось чому O(log n) — максимально швидкий.

🧐 У наступному пості поговоримо про O(n log n) — і як працюють ефективні сортування.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵Наскільки ефективний мій код? 4/8

O(n log n) – Лінійно-логарифмічна складність

Це оптимальна складність для більшості алгоритмів сортування. Ви не зможете стабільно сортувати швидше, ніж O(n log n), якщо не знаєте чогось специфічного про вхідні дані.

📌 Приклад: Сортування злиттям (Merge Sort)

function mergeSort($array) {
    if (count($array) <= 1) return $array;

    $middle = floor(count($array) / 2);
    $left = mergeSort(array_slice($array, 0, $middle));
    $right = mergeSort(array_slice($array, $middle));

    return merge($left, $right);
}

function merge($left, $right) {
    $result = [];
    while (count($left) && count($right)) {
        $result[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);
    }
    return array_merge($result, $left, $right);
}

⛏️ Рекурсія ділить масив навпіл до базового випадку (елемент або два), після чого їх зливає у правильному порядку. Цей підхід дозволяє досягти складності O(n log n) — бо log n — це глибина рекурсії, а n — злиття всіх елементів на кожному рівні.

🧠 Якщо бачите рекурсію + злиття / обʼєднання / ітерацію — майже завжди це O(n log n).

У наступному пості — O(n^2) — і чому вкладені цикли часто погана ідея.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵Наскільки ефективний мій код? 5/8

O(n^2) – Квадратична складність

Це вже повільно. Алгоритми з O(n^2) мають вкладені цикли, і час виконання зростає квадратично відносно розміру вхідних даних.

📌 Приклад: Сортування бульбашкою (Bubble Sort)

function bubbleSort($array) {
    $n = count($array);
    for ($i = 0; $i < $n - 1; $i++) {
        for ($j = 0; $j < $n - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

👀 Кожен елемент перевіряється з кожним — от і квадратична складність. Якщо масив має 1000 елементів — буде до мільйона операцій.

⚠️ Будь-який вкладений цикл — тривожний дзвіночок. У реальному коді O(n^2) трапляється при порівнянні всіх з усіма: наприклад, фільтрація перетинів, дублікати, агрегації без індексів.

🧠 Часом уникнути O(n^2) не вийде, але щойно бачите подвійний цикл — варто хоча б запитати себе: а чи немає кращого способу?

📌 Завтра поговоримо про O(n^3) — кубічну складність. Це вже зовсім важка артилерія.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵Наскільки ефективний мій код? 6/8

O(n³) – Кубічна складність

Тут вже все дуже серйозно. Алгоритми з O(n³) використовують три вкладені цикли. Це означає, що при зростанні розміру даних, час виконання збільшується в кубі.

📌 Приклад: Множення двох матриць

function matrixMultiplication($matrixA, $matrixB) {
    $rowsA = count($matrixA);
    $colsA = count($matrixA[0]);
    $colsB = count($matrixB[0]);

    $result = [];
    for ($i = 0; $i < $rowsA; $i++) {
        for ($j = 0; $j < $colsB; $j++) {
            $result[$i][$j] = 0;
            for ($k = 0; $k < $colsA; $k++) {
                $result[$i][$j] += $matrixA[$i][$k] * $matrixB[$k][$j];
            }
        }
    }
    return $result;
}

📊 Звучить академічно, але трапляється частіше, ніж здається: в обчисленнях, побудові графів, пошуку комбінацій. Усе, що потребує порівняння трійок даних або тривимірних структур — кандидати на O(n³).

⚠️ Це вже критична точка. Якщо можете уникнути такого коду — уникайте. Часто можна знайти способи звести це до O(n²) або навіть O(n log n).

📌 Завтра поговоримо про O(2ⁿ) — експоненціальну складність. І це вже не жарти.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵Наскільки ефективний мій код? 7/8

O(2ⁿ) – Експоненціальна складність

Це вже абсолютна прірва. Зі зростанням обсягу вхідних даних час виконання алгоритму росте дуже швидко. Подвоїли вхід — подвоїли час. І з кожним наступним збільшенням ситуація тільки погіршується.

📌 Приклад: Обчислення чисел Фібоначчі наївним рекурсивним методом

function naiveFibonacci($n) {
    if ($n <= 1) return $n;
    return naiveFibonacci($n - 1) + naiveFibonacci($n - 2);
}

На перший погляд — все просто. Але з кожним викликом функція породжує два нових. І так далі, і далі… Пам’ятаєш кроликів 🐇 Фібоначчі? Ось вони, множаться як божевільні.

💡 У реальних проєктах рекурсивні алгоритми з експоненціальною складністю трапляються рідко, бо майже завжди є ефективніший підхід (динамічне програмування, кешування результатів).

⚠️ O(2ⁿ) — це червоний прапорець. Якщо ви бачите щось подібне у продакшені — час бити на сполох і шукати оптимізацію.

📌 Завтра поговоримо про фінальний босс: O(n!) — факторіальну складність. Таке не пробачається навіть тестових завданнях.

⬅️ Попередня складність | Наступна складність ➡️

#course #algorithm #series

🧵Наскільки ефективний мій код? 8/8

O(n!) – Факторіальна складність

Це — вершина обчислювального кошмару. Факторіальна складність означає, що кількість операцій зростає як добуток усіх цілих чисел до n. Для n = 10 — це вже 3 628 800 варіантів. І так, усе це треба обробити.

10! = 10 × 9 × 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1 = 3 628 800

📌 Приклад: Генерація всіх можливих перестановок елементів

function permutations(array $items): array {
    if (count($items) <= 1) return [$items];

    $result = [];
    foreach ($items as $key => $item) {
        $remaining = $items;
        unset($remaining[$key]);
        foreach (permutations(array_values($remaining)) as $perm) {
            $result[] = array_merge([$item], $perm);
        }
    }
    return $result;
}

Цей код генерує всі можливі перестановки елементів масиву. І якщо їх 8 — то вже 40 320 варіантів. Це може виглядати невинно, поки не впаде прод у Black Friday.

📌 Факторіальна складність — це завжди крайній захід. Якщо задача передбачає перебір усіх варіантів, спершу шукайте апроксимацію, жадібний алгоритм або евристику.


🎬 На цьому серія завершується.
Якщо хочете ще серію подібну до цієї, пишіть в коментарях або в особисті.

⬅️ Попередня складність