Samarqand davlat universiteti raqamli texnologiyalar fakulteti

2-misol. Massiv elementlari yig’indisi
Bir o'lchovli massivning barcha elementlari qiymatlari yig'indisini hisoblaydigan quyidagi algoritm bor deylik:

(1) S=0;

(2) for(int i=0; i(3) S=S+A[i];

Algoritmni bitta satrda bitta operator bo'ladigan tarzda yozish kerak. Bundan tashqari, har bir bajarilgan operator yonida, ushbu operatorning necha marta bajarilishini ko'rsatadigan kirish ma'lumotlarining o'lchamiga bog'liq bo'lgan ifoda yozishingiz kerak. Ushbu baholash ozmi-ko'pmi aniqroq bo'lishi mumkin, asosiysi siz uni xuddi shu tarzda bajarishingiz kerak. Masalan, har bir bayonot bir mavhum vaqt birligida bajarilgan deb taxmin qilishingiz mumkin. Yoki har bir operatorning bajarilishini elementar amallar ketma-ketligiga ajrating: xotiradan o'qing, xotiraga yozing, arifmetik amalni bajaring.
Birinchi yondashuvda biz quyidagi taxminlarni olamiz. Birinchi ifoda bir marta bajariladi va u kiritilgan ma'lumotlarning o'lchamiga bog'liq emas. Ikkinchi operatorning bajarilish soni kiritilgan ma'lumotlarning o'lchamiga bog'liq (xususan, n – massivning uzunligiga). Ushbu holatda bu n + 1 (for siklining boshi uning tanasidan bir marta ko'proq bajarilishini unutmang). Shunga ko'ra uchinchi operator n mavhum vaqt birligida bajariladi. Shunday qilib, bizda:
S=0; (1)

for(int i=0; i

S=S+A[i]; (n)
Barcha operatorlarning algoritmlar murakkabligi yig’indisini hisoblash natijasida 2n + 2 murakkablikni olish mumkin.

Algoritmlarni baholashda ko'pincha quyidagi funktsiyalar qo'llaniladi: , n, , , , , , . ko’rinishida baholangan algoritmlar, har qanday sababga ko'ra, juda tez algoritmlar deb nomlanadi. Bunday algoritmlar unchalik ko'p emas. Aslida, adabiyotda odatda O bahoga ega bo'lgan faqat bitta algoritm zikr qilinadi - bu ikkilik qidiruv algoritmi. Buni keyinroq ko'rib chiqamiz. va deb baholangan algoritmlar tezkor algoritmlar deb ataladi.

O(n²), O(n³) yoki umumiy holatda O(n^C) bo'lgan algoritmlar polinomial algoritmlar deyiladi. Va nihoyat, O(2n), O(10n), O (n!) baholangan algoritmlar polinomial bo'lmagan algoritmlar deyiladi.