Big O — funksiya o‘sishining asimptotik yuqori chegarasini ifodalovchi matematik belgilashdir. Algoritmlar tahlilida u kirish hajmi kattalashganda vaqt yoki xotira talabi qanday o‘sishini tasvirlaydi. Big O aniq sekund, ko‘rsatma soni yoki har bir inputdagi tenglik emas; u yetarlicha katta qiymatlar uchun bound beradi.
Formal ta’rif
f(n) = O(g(n)) deyiladi, agar musbat c va n₀ mavjud bo‘lib, barcha n ≥ n₀ uchun 0 ≤ f(n) ≤ c·g(n) bajarilsa. Constant koeffitsient va kichik ndagi farq bound ichiga singadi.
Masalan, 3n² + 10n + 7 funksiya O(n²). U formal jihatdan O(n³) ham, chunki bu ham yuqori chegara, lekin O(n²) ancha foydali tight tavsifga yaqin. Aniq tight bound uchun Big Theta ishlatiladi.
Keng tarqalgan sinflar
O(1) inputga bog‘liq bo‘lmagan bound, O(log n) har bosqichda muammoni doimiy nisbatda kamaytirish, O(n) barcha elementni bir marta ko‘rish bilan bog‘liq. O(n log n) samarali comparison sortlarda, O(n²) ko‘p juftliklarni tekshirishda uchraydi.
Exponential O(2^n) va factorial O(n!) tez o‘sadi. Kichik n uchun ishlasa ham input biroz kattalashganda amaliy bo‘lmay qoladi. Dynamic programming takroriy subproblemni saqlab, ayrim exponential algoritmni polynomialga tushiradi.
Qoidalar
Ketma-ket bosqichlar narxi qo‘shilib, dominant had olinadi: O(n) + O(n²) = O(n²). Ichma-ich mustaqil sikl ko‘pincha ko‘payadi. Ikki alohida input bo‘lsa O(a·b)ni avtomatik O(n²)ga almashtirish ma’lumotni yo‘qotadi.
Logarithm bazasi Big O’da constant farq qilgani uchun odatda yozilmaydi. log₂ n va log₁₀ n bir asimptotik sinfda. Biroq exponent ichidagi constant, masalan 2^n va 2^(2n)=4^n, oddiy constant koeffitsient emas.
Noto‘g‘ri talqinlar
Big O har doim worst case degani emas. Worst, average yoki amortized holat alohida aytiladi; har biriga Big O bound berish mumkin. O(1) amal ham katta constant, I/O yoki lock kutishini saqlashi mumkin.
Bir xil Big O sinfidagi algoritmlar amalda farq qiladi. Cache locality, branch, vectorization, allocation va input taqsimoti natijaga ta’sir qiladi. Complexity katta masshtabdagi o‘sishni, benchmark esa muayyan qurilma va datasetdagi xatti-harakatni ko‘rsatadi.
Bir nechta parametr
Graph algoritmida vertex V va edge E alohida qoladi: BFS O(V+E). Database query tahlilida jadval qatori, selectivity va index height turli parametr bo‘lishi mumkin. Parametrlarni bitta nga majburlash qaysi o‘lcham bottleneck ekanini yashiradi.
Space complexity uchun ham Big O ishlatiladi. Masalan, merge sort odatda O(n) auxiliary space, in-place heap sort esa O(1) qo‘shimcha space talab qiladi. Vaqt va space tradeoff birgalikda baholanadi.
Parametr qiymati chegarasi
Asimptotik sinf input cheksiz kattalashishini tasvirlaydi, real tizimda esa nning maksimal qiymati ma’lum bo‘lishi mumkin. Masalan, haftaning yetti kuni ustidagi O(n²) sikl amalda doimiy kichik ishdir. Boshqa tomondan, foydalanuvchi nazorat qiladigan JSON depth yoki regex uzunligi kutilmagan katta nga yetib denial of service yaratishi mumkin. API limitlari complexity xavfini operatsion chegaraga aylantiradi. Code reviewda loop soni bilan birga n qayerdan kelishi va kim uni cheklashi ko‘rsatiladi.
Bog‘liq tushunchalar
Big Theta, Big Omega, Time complexity, Space complexity, Asymptotic analysis, Algorithm analysis