Որքա՞ն է Պրիմի ալգորիթմի ժամանակային բարդությունը:
Որքա՞ն է Պրիմի ալգորիթմի ժամանակային բարդությունը:

Video: Որքա՞ն է Պրիմի ալգորիթմի ժամանակային բարդությունը:

Video: Որքա՞ն է Պրիմի ալգորիթմի ժամանակային բարդությունը:
Video: Որդու ծնվելուց հետո մայրիկը մեկ հարց տվեց և ընդմիշտ փակեց աչքերը: 2024, Երթ
Anonim

Այն ժամանակի բարդություն որ Պրիմի ալգորիթմ O ((V + E) l o g V) է, քանի որ յուրաքանչյուր գագաթ տեղադրվում է առաջնահերթ հերթում միայն մեկ անգամ, իսկ առաջնահերթային հերթում տեղադրումը կատարվում է լոգարիթմական ժամանակ.

Բացի այդ, ո՞րն է Կրուսկալ ալգորիթմի ժամանակային բարդությունը:

Բարդություն . Կրուսկալի ալգորիթմը կարող է ցուցադրվել, որ գործարկվի O (E log E) ժամանակ , կամ համարժեք՝ O (E log V) ժամանակ , որտեղ E-ը գծապատկերի եզրերի թիվն է, իսկ V-ը՝ գագաթների թիվը՝ բոլորը պարզ տվյալների կառուցվածքներով։

Նմանապես, ո՞րն է ավելի լավ Prims-ը կամ Kruskal-ը: Կրուսկալի Ալգորիթմ. կատարում է ավելի լավ անտիպ իրավիճակներ (նոսր գրաֆիկներ), քանի որ այն օգտագործում է ավելի պարզ տվյալների կառուցվածքներ: Պրիմի Ալգորիթմ. զգալիորեն ավելի արագ է սահմանում, երբ դուք ունեք իսկապես խիտ գրաֆիկ՝ շատ ավելի շատ եզրային գագաթներով:

Նաև հարցրեց, թե ինչի համար է օգտագործվում Պրիմի ալգորիթմը:

Համակարգչային գիտության մեջ, Պրիմի (նաև հայտնի է որպես Յարնիկի) ալգորիթմ ագահ է ալգորիթմ որը գտնում է նվազագույն ընդգրկող ծառ կշռված չուղղորդված գրաֆիկի համար: Սա նշանակում է, որ այն գտնում է եզրերի ենթաբազմություն, որը կազմում է ծառ, որը ներառում է յուրաքանչյուր գագաթ, որտեղ ծառի բոլոր եզրերի ընդհանուր քաշը նվազագույնի է հասցվում:

Որքա՞ն է զետեղման տեսակավորման ալգորիթմի ժամանակային բարդությունը:

Տեղադրման տեսակավորում ախոռ է տեսակավորել տիեզերքի հետ բարդություն O (1) O (1) O (1). Հետևյալ ցանկի համար, որոնք երկուսը տեսակավորման ալգորիթմներ ունեն նույն վազքը ժամանակ (անտեսելով մշտական գործոնները):

Խորհուրդ ենք տալիս: