Hesablama mürəkkəbliyi nəzəriyyəsində çoxhədli vaxtın azaldılması bir problemin digər istifadə edərək həlli üsuludur. Çoxhədli-zaman azaldılması mürəkkəblik nəzəriyyəsində həm mürəkkəblik siniflərini, həm də bu siniflər üçün tam problemləri müəyyən etmək üçün tez-tez istifadə olunur. …
Çoxhədli vaxt nə hesab olunur?
Əgər alqoritmin işləmə müddəti alqoritm üçün girişin ölçüsündə çoxhədli ifadə ilə yuxarı həddidirsə, alqoritmin polinom zamanlı olduğu deyilir, yəni T(n)=O(Bəzi müsbət sabit k üçün nk).
Bir şeyin çoxhədli zaman olduğunu necə bilirsiniz?
3 Cavablar. Bəzi k, C>0 üçün onun n ölçülü girişlərdə işləmə müddəti ən çox Cnk olarsa, alqoritm çoxhədlidir (polinomlu işləmə vaxtı var). Ekvivalent olaraq, bəzi k>0 üçün onun n ölçülü girişlərdə işləmə müddəti O(nk) olarsa, alqoritm çoxhədlidir.
Əksponensial zamanda azalmaya icazə verilsə nə olar?
Əgər azalmaya eksponensial vaxt verilirsə, o zaman orijinal problemi tam həll edə və hədəf problemin əhəmiyyətsiz bir nümunəsini yarada bilər Bu o deməkdir ki, NP-dəki hər bir problem hər bir problemə endirilə bilər. bu cür azalma növü ilə bağlı digər problem, buna görə də NP-də hər bir problem eksponensial vaxt azalmaları üçün NP-də tamamlanır.
Eksponensial alqoritm nədir?
Alqoritmin eksponensial vaxt olduğu deyilir, əgər T(n) 2poli(ilə yuxarı həddədirsə ) , burada poli(n) n-də bəzi çoxhədlidir. Daha formal olaraq, T(n) bəzi sabit k üçün O(2nk) ilə məhdudlaşırsa, alqoritm eksponensial vaxtdır. Ref:Wiki.
