Algoritmlar samaradorligini tahlil qilish

1. Tahlil asoslari

Asimptotik tahlil
Asymptotic Analysis
Biz haqiqatan ham o'sish sur'atlarini o'lchaganimiz sababli, ayrim jarayonlarga e'tibor bermaymiz:

• "eng katta" atamadan tashqari hammasi va
• har qanday doimiy multiplikatorlar

Misol uchun:
so for example:
λn.0.4n5+3n3+253 oʻzini n5 kabi asimptotik tutadi
λn.6.22nlogn+(n/7) nlogn kabi asimptotik tarzda ishlaydi
Buning asosi quyidagicha:
- Algoritmlarni mavhum ko'rib chiqishda 6n va 3n o'rtasidagi farq mantiqiy emas, chunki agar
siz ikki baravar tez ishlaydigan kompyuterni olsangiz, birinchisi ikkinchisiga o'xshaydi.

• 2n va 2n+8 o'rtasidagi farq n kattalashgani sayin ahamiyatsiz bo'lib qoladi.
• Agar siz, aytaylik, λn.n3 va λn.kn2 ning o'sish sur'atlarini solishtirsangiz,

k ni qanchalik katta qilsangiz ham, birinchisi har doim ikkinchisidan o'tib ketadi.

!!! Buni qanday amalga oshirish mumkin? Ya'ni, "barcha kvadratik funktsiyalar to'plami" yoki "barcha kubik funktsiyalar to'plami" yoki "barcha logarifmik funktsiyalar to'plami" kabi narsalarni qanday amalga oshiramiz?

1. Tahlil asoslari Asimptotik tahlil

Big-O: Asimptotik yuqori chegaralar
Big-O: Asymptotic Upper Bounds
Yani quyidagicha:
Ta`rif: f funktsiya O(g) tegishli deyiladi, qachonki, agar c va N konstantalar mavjud bo'lsa hamda har bir n>N uchun f(n) yuqorida g(n) ning doimiy karrali bilan chegaralangan bo`lsa.
Demak, O(g) barcha funksiyalar to‘plami bo‘lib, ular uchun g f ning asimptotik yuqori chegarasi hisoblanadi.
Examples
Eslatma!
Odatda, insonlar Big-O ishtirokidagi iboralarni yozishda lambdalarni tashlab yuborishadi, shuning uchun siz O(n2) kabi narsalarni ko'rasiz.

1. Tahlil asoslari Asimptotik tahlil