Big O în PHP: timp constant O(1)

Un singur pas, orice dimensiune

O(1) înseamnă timp constant: operația face același număr de pași fie că intrarea are 5 elemente, fie un milion. Volumul de lucru nu crește deloc.

Aceasta este cea mai bună complexitate care există. Operații O(1) tipice în PHP sunt: citirea unui element de tablou după index sau după cheie, count(), adăugarea unui element cu $arr[] = ... și calculele matematice simple.

Observă ce O(1) nu înseamnă: nu înseamnă „rapid”, înseamnă „nu devine mai lent când intrarea crește”. Un singur pas constant poate fi totuși un pas lent — dar rămâne un singur pas.

Căutări după index și după cheie

Un tablou PHP găsește un element direct din cheia lui, așa că $words[2] este un singur salt — motorul nu parcurge elementele dinaintea lui. Aceeași citire costă la fel într-un tablou cu un milion de elemente.

Cheile de tip șir de caractere funcționează în același fel: $ages["Ben"] găsește valoarea direct, în timp constant în medie. O cheie lipsă cere atenție: un simplu $ages["Dan"] generează un avertisment și dă null, așa că citirea sigură este $ages["Dan"] ?? null — operatorul ?? returnează discret valoarea implicită atunci când cheia lipsește.

Citește un element după index

Programul citește un element dintr-un tablou cu 5 elemente și unul dintr-un tablou cu un milion de elemente. Ambele citiri sunt un singur pas — lungimea tabloului nu joacă niciun rol.

Scrie un script PHP cu un tablou mic de 5 cuvinte și un tablou mare de un milion de întregi construit cu o buclă. Citește un element din fiecare după index și afișează-le pe amândouă, pentru a arăta că citirea după index este un singur pas, indiferent cât de lung este tabloul.

> Ieșire: script PHP

Prompt

Scrie un script PHP cu un tablou mic de 5 cuvinte și un tablou mare de un milion de întregi construit cu o buclă. Citește un element din fiecare după index și afișează-le pe amândouă, pentru a arăta că citirea după index este un singur pas, indiferent cât de lung este tabloul.

Ieșire: script PHP

<?php

$words = ["one", "two", "three", "four", "five"];

$big = [];
for ($i = 0; $i < 1000000; $i++) {
  $big[$i] = $i * 2;
}

// Un singur pas fiecare, indiferent cât de lung este tabloul.
echo $words[2], "\n";
echo $big[999999], "\n";

Citește o valoare după cheie

$ages["Ben"] ?? null găsește direct 25. Cheia lipsă "Dan" ajunge la valoarea implicită a lui ?? și dă NULL — tot în timp constant. Fără ??, citirea cheii lipsă ar genera mai întâi un avertisment.

Scrie un script PHP cu un tablou asociativ de la nume la vârste care conține Ana 30, Ben 25 și Cleo 41. Caută Ben folosind valoarea implicită ?? null și afișează rezultatul. Apoi caută în același fel cheia lipsă Dan și afișează din nou rezultatul.

> Ieșire: script PHP

Prompt

Scrie un script PHP cu un tablou asociativ de la nume la vârste care conține Ana 30, Ben 25 și Cleo 41. Caută Ben folosind valoarea implicită ?? null și afișează rezultatul. Apoi caută în același fel cheia lipsă Dan și afișează din nou rezultatul.

Ieșire: script PHP

<?php

$ages = ["Ana" => 30, "Ben" => 25, "Cleo" => 41];

$age = $ages["Ben"] ?? null;
echo "Ben: ", var_export($age, true), "\n";

$age = $ages["Dan"] ?? null;
echo "Dan: ", var_export($age, true), "\n";

Adăugarea și calculele simple

$colors[] = ... adaugă un element la sfârșitul unui tablou. De cele mai multe ori acesta este un singur pas. (Din când în când spațiul de stocare interior trebuie mărit și este copiat, dar, în medie, costul unei adăugări rămâne constant.)

Toate operațiile mărunte — atribuiri, adunări, comparații, interschimbarea a două valori — sunt și ele O(1). Ele sunt „pașii” în care se numără toate celelalte clase de complexitate.

Adaugă un element

$colors[] = "yellow" pune "yellow" la sfârșit. Costul nu depinde de câte culori sunt deja în tablou.

Scrie un script PHP cu un tablou care conține red, green, blue. Afișează tabloul și numărul de elemente, adaugă yellow cu $colors[] = "yellow", apoi afișează din nou tabloul și numărul de elemente.

> Ieșire: script PHP

Prompt

Scrie un script PHP cu un tablou care conține red, green, blue. Afișează tabloul și numărul de elemente, adaugă yellow cu $colors[] = "yellow", apoi afișează din nou tabloul și numărul de elemente.

Ieșire: script PHP

<?php

$colors = ["red", "green", "blue"];
echo "înainte: ", implode(", ", $colors), " (număr: ", count($colors), ")\n";

$colors[] = "yellow";
echo "după:    ", implode(", ", $colors), " (număr: ", count($colors), ")\n";

Interschimbă două valori

[$a, $b] = [$b, $a] interschimbă cele două valori într-un singur pas în timp constant — fără variabilă ajutătoare.

Scrie un script PHP cu două variabile a = 1 și b = 2. Afișează-le, interschimbă-le cu atribuirea prin listă [$a, $b] = [$b, $a] și afișează-le din nou.

> Ieșire: script PHP

Prompt

Scrie un script PHP cu două variabile a = 1 și b = 2. Afișează-le, interschimbă-le cu atribuirea prin listă [$a, $b] = [$b, $a] și afișează-le din nou.

Ieșire: script PHP

<?php

$a = 1;
$b = 2;
echo "înainte: $a $b\n";

[$a, $b] = [$b, $a];
echo "după:    $a $b\n";