Ինչպե՞ս է հաշվարկվում միավորման տեսակավորման բարդությունը:

2024 Հեղինակ: Lynn Donovan | [email protected]. Վերջին փոփոխված: 2023-12-15 23:48

2 Պատասխաններ. A[L, R] հանգույցը երկու հանգույցի բաժանելու համար պահանջվում է R−L+1 ժամանակ, իսկ հետո միաձուլում A[L, M] և A[M+1, R] երկու երեխա հանգույցները կրկին պահանջում են A[R−L+1] ժամանակ: Այսպիսով, յուրաքանչյուր հանգույցի համար գործողությունների քանակը ալգորիթմ կատարումը հավասար է այդ հանգույցին համապատասխան զանգվածի կրկնակի չափին:

Այս առնչությամբ ինչպե՞ս է աշխատում միաձուլման տեսակավորումը:

Ահա, թե ինչպես է միաձուլման տեսակավորումը օգտագործում բաժանել և նվաճել

1. Բաժանեք՝ գտնելով դիրքի q թիվը p-ի և r-ի միջև:
2. Նվաճել՝ ռեկուրսիվորեն դասավորելով ենթազանգվածները բաժանման քայլով ստեղծված երկու ենթախնդիրներից յուրաքանչյուրում:
3. Միավորել՝ միաձուլելով երկու տեսակավորված ենթազանգվածները մեկ տեսակավորված ենթազանգվածի մեջ[p..

Նաև, ո՞րն է միաձուլման տեսակավորման մեծ O բարդությունը: Միաձուլման տեսակավորում ախոռ է տեսակավորել ինչը նշանակում է, որ զանգվածի միևնույն տարրը պահպանում է իրենց սկզբնական դիրքերը միմյանց նկատմամբ: Ընդհանուր ժամանակ բարդություն -ից Միաձուլման տեսակավորում է Օ (nLogn): Այն ավելի արդյունավետ է, քանի որ վատագույն դեպքում նաև գործարկման ժամանակն է Օ (nlogn) Տարածությունը բարդություն -ից Միաձուլման տեսակավորում է Օ (n).

ո՞րն է միաձուլման տեսակավորման բարդությունը վատագույն դեպքում:

n*log(n)

Քանի՞ համեմատություն է կատարում միաձուլման տեսակավորումը:

Երբ ցուցակներից մեկի տարրերը սպառվում են, մնացած տարրերը դնում ենք ցուցակի վերջին անցքերի մեջ տեսակավորված ցուցակը։ Որպես արդյունք, միաձուլում երկու ցուցակ, որոնք ունեն ընդհանուր n տարր, պահանջում են առավելագույնը n-1 համեմատություններ.