Big O Notation nima?

Big O Notation (O katta notatsiyasi) — bu algoritmlarning vaqt va xotira (memory) murakkabligini ifodalovchi matematik formuladir. Bu notatsiya yordamida algoritmning eng yomon holatda qanday ishlashini tahlil qilamiz.

Nega Big O muhim?

• Katta hajmdagi ma’lumotlar bilan ishlaganda sekin ishlaydigan kodlar muammoga aylanadi.
• Big O bizga algoritmlarni solishtirish va optimizatsiya qilish imkonini beradi.

Asosiy Big O turlari

1. O(1) — Constant Time (Doimiy vaqt)

Kiruvchi ma’lumotlar soni qancha ko‘p bo‘lsa ham, bajarilish vaqti o‘zgarmaydi.

function getFirstElement(arr) {
  return arr[0];
}

2. O(n) — Linear Time (Chiziqli vaqt)

Ma’lumotlar soni oshgan sari bajarilish vaqti ham shu nisbatda oshadi.

function logAllElements(arr) {
  for (let i = 0; i < arr.length; i++) {
    console.log(arr[i]);
  }
}

3. O(n²) — Quadratic Time (Kvadratik vaqt)

Har bir element uchun yana n ta operatsiya bajariladi.

function printPairs(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length; j++) {
      console.log(arr[i], arr[j]);
    }
  }
}

4. O(log n) — Logarithmic Time

Har bir bosqichda ma’lumotlar hajmi yarmiga qisqaradi.

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

5. O(n log n) — Efficient Sorting Algorithms

Masalan, Merge Sort yoki Quick Sort algoritmlarida tezlik shu tarzda ifodalanadi.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;
  while (l < left.length && r < right.length) {
    result.push(left[l] < right[r] ? left[l++] : right[r++]);
  }
  return result.concat(left.slice(l)).concat(right.slice(r));
}

6. O(2ⁿ) — Exponential Time

Har bir chaqiruvda 2 ta yangi chaqiruv yuzaga keladi.

function fibonacci(n) {
  if (n <= 1) return n;
  return fibonacci(n - 1) + fibonacci(n - 2);
}

Jadval: Asosiy Big O lar taqqoslanishi

Bonus: Space Complexity (Xotira murakkabligi)

Big O faqat vaqt emas, xotira ishlatilishini ham o‘lchash uchun ishlatiladi.

function sumArray(arr) {
  let sum = 0; // O(1) space
  for (let i = 0; i < arr.length; i++) {
    sum += arr[i];
  }
  return sum;
}

function doubleArray(arr) {
  const result = []; // O(n) space
  for (let i = 0; i < arr.length; i++) {
    result.push(arr[i] * 2);
  }
  return result;
}

Xulosa

Big O Notation — bu kodlarimizni tahlil qilish, optimallashtirish va solishtirish uchun juda muhim vosita. Har bir dasturchi algoritm yozishda bu tushunchani hisobga olishi zarur.