Złożoność, którą da się narysować

Dobry artykuł techniczny nie zaczyna się od ściany kodu. Najpierw jest pytanie, potem miara, a dopiero na końcu implementacja. Tu miarą jest liczba operacji dominujących, zapisana jako

Co naprawdę liczymy

• Czas — ile kroków robi procesor, gdy wejście rośnie.

• Pamięć — ile dodatkowych komórek dokładamy obok samego wejścia.

• Stabilność zapisu — czy stałe i cache nie wywracają asymptotyki na małych n.

Notacja jest sufitem: algorytm mieści się pod dla dostatecznie dużych . To nie jest obietnica, że każda stała jest nieważna — tylko że kształt krzywej już się nie zmieni.

Klasy, które wracają w kodzie

Klasa

Skąd się bierze

Przykład

O(1)

jedno sięgnięcie pod indeks

tablica haszująca, średnio

O(log n)

połowa odpada w każdym kroku

binarne szukanie

O(n)

jeden raz przez całość

filtr liniowy

O(n log n)

podział i scalanie

mergesort

O(n²)

para zagnieżdżonych pętli

naiwne przecięcie

Twierdzenie mistrzów

Gdy problem rozpada się na podproblemów rozmiaru , a praca poza rekurencją to , całość spełnia:

Dla mergesorta , i , więc . Wzór jest krótkim zdaniem o kształcie drzewa wywołań.

Najpierw drzewo, potem pętla

To samo drzewo da się przejść na kartce. Diagram jest tylko po to, żeby czytelnik nie zgubił gałęzi.

1. Wskaż operację, która dzieje się najczęściej.

2. Policz, ile razy wykona się dla wejścia n.

3. Porównaj z klasą z tabeli, zanim ruszysz profiler.

function binarySearch(xs: readonly number[], target: number): number {
  let lo = 0;
  let hi = xs.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (xs[mid] === target) return mid;
    if (xs[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

Asymptotyka mówi, jak krzywa się ugina. Pomiar mówi, gdzie ugięła się dzisiaj.

Dalszy ciąg rozmowy: #programowanie.