Big-O azt írja le, hogyan növekszik egy algoritmus futási ideje vagy memóriahasználata, ahogy a bemeneti méret n növekszik. Megragadja a legrosszabb eseti aszimptotikus viselkedést, figyelmen kívül hagyva az konstansokat és az alacsonyabb rendű tagokat.
A növekedési rátára vagyunk kíváncsiak, nem a pontos lépések számára. Az O(2n + 5) egyszerűen O(n), mert ahogy n nagy lesz, a konstansok és a kisebb tagok már nem számítanak.
| Big-O | Név | Példa |
|---|---|---|
| O(1) | konstans | tömb indexelés |
| O(log n) | logaritmikus | bináris keresés |
| O(n) | lineáris | lista végigpásztázása |
| O(n log n) | linearitmikus | merge sort |
| O(n²) | kvadratikus | beágyazott ciklusok |
| O(2ⁿ) | exponenciális | naiv részhalmazok |
def has_duplicate(nums):
for i in range(len(nums)): # outer loop: n
for j in range(i + 1, len(nums)): # inner loop: n
if nums[i] == nums[j]:
return True
return False
# nested loops -> O(n^2) time, O(1) space
A Big-O elrejti a konstansokat: egy óriási konstanssal rendelkező O(n) algoritmus elveszíthet egy O(n log n) algoritmussal szemben kis bemeneteken. Figyeljen a tér komplexitásra is, nem csak az időre.
A Big-O lehetővé teszi algoritmusok összehasonlítását anélkül, hogy futtatnád őket vagy a hardverre gondolnál.
Megjósolja, mely megoldások maradnak életben, amikor a bemenetek százról millióra növekednek — a különbség egy skálázható funkció és egy, amely időtúllépést jelent.
Ez az a szókincs, amelyet minden mérnök használ a teljesítmény megosztásához.