Algoritmlar samaradorligini tahlil qilish

Big-O: Asimptotik yuqori chegaralar
Big-O: Asymptotic Upper Bounds
Big-O foydalimi?

• Big-O yozuvi faqat katta n uchun eng foydali hisoblanadi. Past tartibli atamalar va

etakchi konstantalarni bostirish kichik n uchun noto'g'ri.
Quyidagi ko`rinishdagi funktsiyalardan ehtiyot bo'ling:
2. Katta konstantalar muhimroq shartlarda, masalan, taqqoslashda qo'shimcha
xarajatlarni bildiradi. 8nlogn va 0.01n2 E'tibor bering, birinchi variant n 10 710 ga
yetguncha yomonroq.

3. Sedgewick yozadi: “[Big-O tahlili] uning xususiyatlari haqida ko'proq ma'lumot berish uchun algoritm tahlilini takomillashtirishning progressiv jarayonidagi birinchi qadam deb hisoblanishi kerak”
4. Big-O - bu faqat yuqori chegara; u tor yuqori chegara emas. Agar algoritm O(n2) da boʻlsa, u O(n3), O(n100) va O(2n) da ham boʻladi. Demak, O(2n)dagi barcha murakkablik funktsiyalari daxlsiz deb aytish toʻgʻri emas, chunki bu toʻplam O(1) toʻplamini oʻz ichiga oladi.

1. Tahlil asoslari Asimptotik tahlil

Big-Ω: Asimptotik pastki chegaralar
Big-Ω: Asymptotic Lower Bounds
Pastki chegaralar uchun Big-Ω belgisi mavjud.
Ta`rif: f funksiya Ω (g) ga tegishli deyiladi, qachonki agar c va N konstantalar mavjud bo'lsa, hamda har bir n>N uchun f(n) pastdan g(n) ning doimiy karrali bilan chegaralangan bo'lsa.
Yani quyidagicha:
Pastki chegaralar foydalidir, chunki ular algoritm kamida shuncha vaqtni oladi, deb aytishadi. Masalan, siz massivni chop etishni O(2n) deb aytishingiz mumkin, chunki 2n haqiqatan ham yuqori chegara, unchalik qattiq emas! Ammo massivni chop etish Ω (n) ni aytish, bu kamida chiziqli vaqtni talab qiladi, bu aniqroqdir. Albatta, deyarli hamma narsa Ω(1) qiymatiga ega.

1. Tahlil asoslari Asimptotik tahlil

Big-Θ
Pastki va yuqori chegaralar bir xil bo'lsa, biz Big Theta (Big-Θ) yozuvidan foydalanishimiz mumkin.
Yani quyidagicha:
Misol: massivning har bir elementini chop etish - Θ (n). Mana bu foydali!
Example: printing each element of an array is Θ (n). Now that’s useful!
Homework:
Amalda yuzaga keladigan murakkablik funktsiyalarining aksariyati biror narsaning Big-Thetasida. Har qanday narsaning Big-Θ da bo'lmagan funksiyaga λn.n2cosn misol bo'ladi.