Algoritmni optimallashritish usullari

Intervyuda beriladigan masalalarni yechishda avvalambor, "Brute Force", ya'ni unchalik optimal bo'lmagan, lekin ishlaydigan yechim berish kerak. Keyinchalik shu "Brute Force" yechimni qanday qilib optimallashtirish mumkin? Aslida sizni intervyu qiladigan odam ham shuni kutib turadi va ko'p hollarda optimal yechimga olib boradigan ishoralar berishga harakat qiladi.
Buning birinchi usullaridan biri: "BUD".

BUD usuli

BUD - quyidagi so'zlarning bosh harflaridan tuzilgan:

• Bottlenecks
• Unnecessary work
• Duplicated work

"Bottlenecks" - to'siqlar. Bu algoritm hisoblanishiga ketadigan vaqtni sekinlashtirayotgan qismidir.
Masalan: bizda mavjud ko'p qismli algoritmning 1-qismi berilgan massivni saralasin, 2-qismi esa saralangan massivdan ma'lum bir elementni topsin. Algoritm hisoblanishiga ketadigan vaqt 1-qismda O(n*log(n)), 2-qismda O(n) bo'lsin. Ko'rinib turibdiki, algorimning 1-qismi algoritm hisoblanish vaqtini sekinlashtiryapti. Agar biz uni optimallashtiradigan bo'lsak, algoritmni optimallashtirgan bo'lamiz.

Masala:
Butun sonlardan tashkil topgan va bo'sh bo'lmagan massiv berilgan bo'lsin. Massivda bir elementdan tashqari har bir element ikki martadan qatnashadi. Takrorlanmagan elementni topish va uni qaytarish kerak.

Yechish:
Birinchi bo'lib hayolga keladigan yechim quyidagicha bo'lishi mumkin:

function singleNumber (nums) {
    nums.sort((a, b) => a - b);

    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== nums[i - 1] && nums[i] !== nums[i + 1]) {
            return nums[i];
        }
    }
};

Demak, biz avvalambor berilgan massivimizni o'sish tartibida saralab oldik. JavaScriptning sort() metodi O(n*log(n)) o'rtacha hisoblash vaqtiga ega, bu yerda n massiv uzunligidir. Keyingi sikl esa har bir elementni tekshiradi va agar massiv elementi undan oldingi va keyingi elementlarga teng bo'lmasa, shu elementni qaytaradi. Bu sikl O(n) chiziqli hisoblash vaqtiga ega.
Funksiyaning umumiy hisoblash vaqti O(n*log(n)) + O(n) bo'lib, O(n*log(n))ga soddalashadi. Bu funksiyamizdagi hisoblash vaqtini sekinlashtirayotgan qismi - massivni saralagan qismimizdir. Umuman olganda, bizga massivni saralashimiz kerakmi? Masalani massivni saralamasdan ham yecha olamizmi?

Endi "Brute Force" yechimimizni optimallashtirishga o'tamiz.

function singleNumber(nums) {
  let singleNum = 0;

  for (let num of nums) {
    singleNum ^= num;
  }

  return singleNum;
}

Ushbu optimallashtirilgan algoritmimizda biz massivning har bir elementini ko'rib chiqyapmiz va bitli XOR operatoridan ^ foydalangan holda singleNum o'zgaruvchimizga qo'shib bormoqdamiz. Raqamni o'zi bilan XOR lash 0 qiymatini beradi, shuning uchun takroriy raqamlar mavjud bo'lganda, ular 0 bo'lib ketadi va faqatgina takrorlanmagan raqam qoladi. Bu esa umumiy O(n) hisoblash vaqtini oladi.

Unnecessary work - keraksiz ish. Biz algoritmimizda biror-bir keraksiz ishni amalga oshiryapmizmi?

Masala:
Quyidagi ikki xususiyatga ega (m x n) butun sonlar matritsasi berilgan:

• Har bir qator kamaymaydigan tartibda tartiblangan.
• Har bir satrning birinchi butun soni oldingi qatorning oxirgi butun sonidan kattaroqdir.

Masalan:

Butun son target berilgan bo'lsa, agar target matritsada bo'lsa, true, aks holda false qaytarish kerak.

Yechish:
"Brute Force" yechim quyidagicha bo'lishi mumkin:

function searchMatrix(matrix, target) {
    for(let i = 0; i < matrix.length; i++) {
        for(let j = 0; j < matrix[i].length; j++) {
            if(matrix[i][j] === target) return true;
        }
    }
    return false;
 };

Bunda biz matritsani har bir elementini berilgan targetga teng yoki teng emasligini tekshirish uchun ichma-ich for sikllaridan foydalanyapmiz. Bu algoritmning hisoblash vaqti O(m*n), m - matritsaning qatorlar soni, n - matritsaning ustunlari soni. Aslida, keraksiz ishni amalga oshiryapmiz. Bizga matritsa elementlari ma'lum bir tartibda saralangani haqidagi ma'lumotdan foydalanmayapmiz, ya'ni keraksiz ishni bajaryabmiz.
Matritsaning elementlari ma'lum bir qoida asosida saralangani haqidagi ma'lumotni inobatga olib, biz quyidagi yechimni berishimiz mumkin:

function searchMatrix(matrix, target) {
  const numRows = matrix.length;
  const numCols = matrix[0].length;
  let left = 0;
  let right = numRows * numCols - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    const midElement = matrix[Math.floor(mid / numCols)][mid % numCols];

    if (midElement === target) {
      return true;
    } else if (midElement < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  return false;
}

Ma'lumki, saralangan massivdan biror-bir elementni topish uchun "Binary search" algoritmidan foydalanish samaralidir. Ushbu yondashuvda element har doim massivning o'rtasidan qidiriladi. Bizda matritsa bo'lganligi uchun matritsaning o'rta elementini topish hisob-kitoblarimiz biroz boshqacharoq bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan kichik bo'lsa bizga matritsaning o'rta elementidan chap qismi kerak emas, ularni tashlab yuborsak bo'ladi. Agar matritsaning o'rta elementi qidirilayotgan elementdan katta bo'lsa bizga matritsaning o'rta elementidan o'ng qismi kerak emas, ularni tashlab yuborsak bo'ladi. Shunday yo'l bilan biz matritsadan ma'lum bir elementni qidirishni optimallashtirdik. Bunda algoritm hisoblanishiga ketadigan vaqt O(log(m*n)).

Duplicated work - takroriy ish. Algoritmda biror-bir ishni takroran bajaryapmizmi?

Masala:
n-chi fibonacci sonini qaytaring.

Yechim:

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

    return fibonacci(n - 1) + fibonacci(n - 2);
}

Ushbu funksiya fibonacci sonlar ketma-ketligidan n-sonni qaytaradi. Bu sonlar ketma-ketligi - har bir raqam oldingi ikkitasining yig'indisi bo'lgan raqamlar qatoridir. U 0 va 1 dan boshlanadi va keyingi raqamlar oldingi ikkita raqamni qo'shish orqali hosil bo'ladi. Masalan:
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
Biroq, buni amalga oshirishda, funktsiya bir xil fibonacci raqamlarini bir necha marta qayta-qayta hisoblab chiqadi, ya'ni takroriy ishni bajaryapmiz. Algoritm hisoblanishiga ketadigan vaqt O(2^n). Uni qanday optimallashtirishimiz mumkin?

Biz qo'shimcha xotiradan foydalanishimiz mumkin:

function fibonacci(n) {
    let memo = {};
    return fibonacciHelper(n, memo);
}

function fibonacciHelper(n, memo) {
    if (n <= 1) {
        return n;
    }

    if (memo[n]) {
        return memo[n];
    }

    memo[n] = fibonacciHelper(n - 1, memo) + fibonacciHelper(n - 2, memo);
    return memo[n];
}

fibonacciHelper funksiyasi argument sifatida n va memoni qabul qiluvchi rekursiv yordamchi funksiyadir. fibonacciHelper funktsiyasi ichida biz berilgan n uchun fibonacci raqami memo ob'ektida mavjudligini tekshiramiz. Agar u mavjud bo'lsa, biz memo ob'ektidan oldindan hisoblangan qiymatni qaytaramiz. Agar fibonacci raqami memo ob'ektida mavjud bo'lmasa, u fibonacci raqamini rekursiv hisoblab chiqadi. Hisoblangan fibonacci raqami keyinchalik ma'lumot sifatida memo ob'ektida saqlanadi va qaytariladi.
Qo'shimcha xotiradan foydalangan holda oldindan hisoblangan fibonacci raqamlarini saqlash orqali takroriy ishlarni oldini olamiz. Bu fibonacci hisobining samaradorligini sezilarli darajada yaxshilaydi. Algoritm hisoblanishiga ketadigan vaqt O(n). Bu yaxshilanishga avvaldan hisoblangan fibonacci raqamlarini saqlash yordamida ortiqcha hisob-kitoblarni yo‘q qilish orqali erishildi.

Xulosa:

BUD optimallashtirish usuli - "to'siqlar, keraksiz ish va takroriy ish" degan ma'noni anglatadi va algoritmlar yoki kodlardagi samarasizlikni aniqlash va bartaraf etish uchun ishlatiladigan printsipdir. Ushbu usul "Brute Force" yechimini ishlab chiqqandan keyingi birinchi variantlardan biri bo'lishi kerak. Chunki u algoritmning hisoblash vaqtini yaxshilash usullarini aniqlashga qaratilgandir.