Axılma polinom vaxtıdır?

2024 Müəllif: Fiona Howard | [email protected]. Son dəyişdirildi: 2024-01-10 06:34

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 n^k).

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) 2^{poli(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(2^{nk) ilə məhdudlaşırsa, alqoritm eksponensial vaxtdır. Ref:Wiki.}