Big-O inaeleza jinsi muda wa utekelezaji au kumbukumbu ya algoritm inaongezeka kadri ukubwa wa data n inavyoongezeka. Inakamatia tabia ya hali mbaya zaidi asymptotika, ikipuuza mara kwa mara na masharti ya utaratibu wa chini.
Tunajali kwa kiwango cha ukuaji, si hesabu sawa ya hatua. O(2n + 5) ni kwa urahisi O(n) kwa sababu kadri n inavyokuwa kubwa, mara kwa mara na masharti madogo hayakuwepo na maana.
| Big-O | Jina | Mfano |
|---|
| O(1) | isiyobadilika | kuangalia faharasa ya array |
| O(log n) | logarithmic | utafutaji wa binary |
| O(n) | mstari | kusambaza orodha |
| O(n log n) | linearithmic | merge sort |
| O(n²) | mraba | loops zilizowekwa |
| O(2ⁿ) | aina kielelezo | subsets za naive |
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
Big-O inahifadhi mara kwa mara: algoritm ya O(n) yenye mara kwa mara kubwa inaweza kupoteza kwa O(n log n) kwenye data ndogo. Pia fuatilia utata wa space, si muda tu.
Big-O inakuruhusu kulinganisha algorithms bila kuzitekeleza au kuwa na wasiwasi juu ya hardware.
Inakamatia suluhu gani zitakamatica kadri data inavyoongezeka kutoka mamia hadi mamilioni — tofauti kati ya bailifu inayobadilika kwa saizi na moja inayozinga.
Ni msamiati ambao kila mhandisi hutumia kufikiri kuhusu utendaji.