Կրճատման ժամանակը բազմանդամ է:

2024 Հեղինակ: Fiona Howard | [email protected]. Վերջին փոփոխված: 2024-01-10 06:38

Հաշվարկային բարդության տեսության մեջ բազմանդամ-ժամանակի կրճատումը մեթոդ է մի խնդիր լուծելու համար՝ օգտագործելով մեկ այլ: Բազմանդամային ժամանակի կրճատումները հաճախ օգտագործվում են բարդության տեսության մեջ՝ ինչպես բարդության դասերը, այնպես էլ այդ դասերի ամբողջական խնդիրներ սահմանելու համար: …

Ի՞նչ է համարվում բազմանդամ ժամանակ:

Ալգորիթմը կոչվում է բազմանդամ ժամանակի, եթե դրա գործարկման ժամանակը վերին սահմանափակված է ալգորիթմի մուտքագրման չափի բազմանդամ արտահայտությամբ, այսինքն՝ T(n)=O(n^k) որոշ դրական հաստատուն k.

Ինչպե՞ս գիտեք, որ ինչ-որ բան բազմանդամ ժամանակ է:

3 Պատասխաններ: Ալգորիթմը բազմանդամ է (ունի բազմանդամ գործարկման ժամանակ), եթե որոշ k-ի համար՝ C>0, նրա գործարկման ժամանակը n չափի մուտքերում առավելագույնը Cnk է: Համարժեքորեն, ալգորիթմը բազմանդամ է, եթե որոշ k>0-ի համար n չափի մուտքերում դրա գործարկման ժամանակը O(nk է):

Ի՞նչ տեղի կունենա, եթե կրճատումը թույլատրվի էքսպոնենցիալ ժամանակում:

Եթե կրճատումը թույլատրված է էքսպոնենցիալ ժամանակով, ապա այն կարող է լիովին լուծել սկզբնական խնդիրը և ստեղծել թիրախային խնդրի չնչին օրինակ Սա նշանակում է, որ NP-ի յուրաքանչյուր խնդիր կրճատելի է յուրաքանչյուրի համար: Նման տեսակի կրճատումների այլ խնդիր, ուստի NP-ի յուրաքանչյուր խնդիր NP-լրիվ է ժամանակի էքսպոնենցիալ կրճատումների համար:

Ի՞նչ է էքսպոնենցիալ ալգորիթմը:

Ալգորիթմը համարվում է էքսպոնենցիալ ժամանակ, եթե T(n)-ը վերևում սահմանազատված է 2^{բազմաթիվ( )} , որտեղ poly(n)-ը որոշ բազմանդամ է n-ում: Ավելի ձևականորեն, ալգորիթմը էքսպոնենցիալ ժամանակ է, եթե T(n)-ը սահմանափակված է O(2^{nk) ինչ-որ հաստատուն k-ի համար:Հղում:Wiki.}