Skip to content

Big O - nima?

Big O - bu yozilgan algoritm qanchalik samaradorligini aniqlovchi o'lchov. Bu o'lchov algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon qanday o'zgarishini taqribiy ko'rsatadi.

Info

Big O - Algoritm tezligini baholash standarti.

  • Birligi - Operatsiyalar soni
  • Eng yomon holat uchun baholaydi

Algoritmlarni baholash uchun odatda 3 xil o'lchov birligidan foydalaniladi.

  1. Big O notation: Vaqt va Xotira murakkabligini eng maksimum qiymatini o'lchash uchun ishlatiladi. Uning vazifasi bizning Algoritm yoki Ma'lumotlar struktuamiz eng yomon holat(worst-case)da qanday ishlashini tasvirlaydi.
  2. Theta notation: Vaqt va Xotira murakkabligini o'rtacha holatini o'lchash uchun ishlatiladi.
  3. Omega notation: Vaqt va Xotira murakkabligini eng minimum qiymatini o'lchash uchun ishlatiladi. Uning vazifasi bizning Algoritm yoki Ma'lumotlar struktuamiz eng yaxshi holat(best-case)da qanday ishlashini tasvirlash.

Dasturlarni odatda worst-case holati o'lchanadi. Chunki bu orqali siz o'z dasturingiz eng yomon holatda qanday ko'rsatgichda ishlashini bilib olasiz. Bu huddi marafon yuguruvchisi kasal va yugurishga loyiq emas holatida qanday natija ko'rsatishini o'lchashdek gap. Demak biz Big O notation nima uchun xizmat qilishini qisman tushunib oldik endi keling to'liqroq misollar bilan ko'rib chiqsak.

O'lchovlar

  1. O(1) - algoritmga kiruvchi qiymatlar o'sib borsa ham, algoritm hisoblanishiga ketadigan vaqt yoki maydon o'zgarmasdan qolishini anglatadi.
  2. O(n) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon ham birdek o'sib borishini anglatadi. Masalan: Agar biz algoritmda n o'lchamdagi massiv yaratsak, algoritm O(n) joy talab qiladi.
  3. O(log(n)) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon logarifmik ravishda o'sadi.
  4. O(2^n) - algoritmga kiruvchi qiymatlar o'sib borishi bilan algoritm hisoblanishiga ketadigan vaqt yoki maydon eksponensial ravishda ortib boradi.

Big Oni o'rganishlarimiz davomida amaliyotda ko'rib o'tamiz.

Baholash

  • CPU 2.5GHz 10^9 mlrd hz - 1 secondda 2.5 mlrd operatsiya bajaradi
  • T=1/F=0.4x10^-9=0.4ns
  • Misol
  • N=1.5 mlrd
  • LS: TxN=0.4ns x 1.5 x 10^9=0.6s
  • BS: Log2N=0.4ns x 30=12ns
  • Summary: farqi 50mln

Big O - Order Complexity O'lchov birligi operatsiyalar soni