1. Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar

2.5.2 NP- qiyin vaNP- Vazifalarni bajaring.
P dagi muammo NP- qiyin agar uning yechimining DA (PDA) polinomi mavjud bo'lsa, undan NPga kiritilgan barcha masalalarning yechimini olish uchun foydalanish mumkin. Ya'ni, bunday muammo NP-qiyin, agar u hech bo'lmaganda NPdagi har qanday muammo kabi qiyin bo'lsa.
NP ga tegishli NP-qiyin masala deyiladi NP-to'la vazifa. Bunday muammolar har qanday NP muammosidan kam emas. Bundan tashqari, NP-qattiq yoki NP-to'liq masala uchun PDA mavjudligi P va NP sinflarining mos kelishini anglatadi, ya'ni 3-sinfning barcha masalalarini tezkor algoritm bilan hal qilish mumkin.
Muammoning NP-qiyinligini isbotlash uchun, agar muammo uchun PDA mavjud bo'lsa, u holda NPga kiritilgan muammolarning boshqa PDA yechimini olish uchun ishlatilishi mumkinligini ko'rsatish kerak.
Muammoning NP-to'liq ekanligini aniqlash uchun uning NPga tegishli ekanligini isbotlash kerak.
Bir masalani yechish algoritmidan boshqasini yechish algoritmini olish uchun foydalanish g‘oyasi algoritmlar nazariyasidagi eng muhim algoritmlardan biridir.
Ta'rif 1: R1 masala R2 muammosiga aylantiriladi, agar R1 muammoning har qanday maxsus holatini ko'pnomli vaqtda R2 muammosining qandaydir maxsus holatiga aylantirish mumkin bo'lsa. U holda R1 yechimini R2 muammoning xususiy holining yechimidan ko‘pnomli vaqtda olish mumkin.
https://pandia.ru/text/78/183/images/image024_39.gif "kenglik =" 158 balandlik = 56 "balandlik =" 56 ">
Masalan:
f2 (xi)=(x1 Ú x2 ) Ù ( ) Ù ()
mumkin emas, chunki hech kim uchun xi f2 (xi)= yolg'on.
Algoritmni buyurtma qilishning murakkabligini baholash algoritmlar murakkabligining yuqori chegarasidir. Agar dastur katta murakkablik darajasiga ega bo'lsa, bu algoritm haqiqatan ham uzoq davom etadi degani emas. Ba'zi bir ma'lumot to'plamlarida, algoritmni bajarilishi ularning murakkabligi asosida taxmin qilishdan ancha kam vaqt talab etadi. Masalan, A vektorda berilgan elementni qidiradigan kodni ko'rib chiqing. Agar kerakli element ro'yxatning oxirida bo'lsa, unda dastur N bosqichni bajarishi kerak bo'ladi. Bunday holda, algoritmning murakkabligi O (N) dir. Ushbu eng yomon holatda, algoritmning ishlash vaqti maksimal bo'ladi. Boshqa tomondan, kerakli narsa birinchi holatda ro'yxatda bo'lishi mumkin. Algoritm faqat bitta qadamni bajarishi kerak. Bunday holat eng yaxshi deb nomlanadi va uning murakkabligi O (1) deb baholanishi mumkin.
function Locate(data: integer): integer;
var i:
integer;
fl:
boolean;
begin
fl:=false;
i:=1;
while (not fl) and (i<=N) do
begin
if A[i]=data then
fl:=true else
i:=i+1;
end;
if not fl then
i:=0;
Locate:=I;
end;
Ushbu ikkala holat ham mumkin emas. Bizni kutilgan variant ko'proq qiziqtiradi. Agar ro'yxat elementi dastlab tasodifiy aralashtirilsa, unda kerakli element ro'yxatning istalgan joyida paydo bo'lishi mumkin. O'rtacha, kerakli elementni topish uchun N / 2 taqqoslash talab qilinadi. Shunday qilib, ushbu algoritmning murakkabligi o'rtacha O (N / 2) = O (N).
Bunday holda, o'rtacha va kutilgan murakkablik bir xil, ammo ko'plab algoritmlar uchun eng yomon holat kutilganidan juda farq qiladi. Masalan, eng yomon holatlarda tez tartiblash algoritmi O (N ^ 2) tartibining murakkabligiga ega, kutilayotgan xattiharakatlar esa O (N * log (N)) bahosi bilan tavsiflanadi, bu ancha tezroq


Teorema :
Qoniqish muammosi NP-to'liq.
xi tanlash (to'g'ri, noto'g'ri)
agar E (x1, x2,…, xN) bo'lsa, muvaffaqiyat
boshqa muvaffaqiyatsizlik
P1 muammosini P2 ga aylantirishdan foydalanib, qoniqish muammosining cheklangan holati ham NP-to'liq ekanligini ko'rsatish mumkin.