Բառը[Թաքցնել][Ցուցադրում]
Համակարգչային գիտությունն ուղղված է ալգորիթմների և տվյալների կառուցվածքների բարդությունների ըմբռնմանը:
Դուք ունեք ապրանքների ցանկ, որոնք պետք է տեսակավորվեն, բայց դուք ժամանակ կամ ռեսուրսներ չունեք տեսակավորման ավելի բարդ ալգորիթմ օգտագործելու համար:
Տեղադրման տեսակավորումը դասակարգման ամենապարզ ալգորիթմներից մեկն է, բայց այն կարող է դանդաղ լինել մեծ ցուցակների համար:
Հեշտ իրականացումը և ըմբռնումը այս մեթոդը դարձրել են սիրելի ծրագրավորողների շրջանում: Այն կատարյալ է փոքր ցուցակների համար կամ երբ ձեզ արագ լուծում է պետք:
Այս բլոգի գրառման մեջ մենք կանդրադառնանք ներդիրների տեսակավորման ժամանակային բարդությանը: Այս ալգորիթմը օգտագործվում է զանգվածները տեսակավորելու համար և ունի O(n2) Սա նշանակում է, որ ժամանակի բարդությունը մեծանում է զանգվածի չափի հետ։
Այնուամենայնիվ, այս ալգորիթմը կարող է ավելի արագ լինել, քան այլ տեսակավորման ալգորիթմները, ինչպիսիք են արագ տեսակավորումը:
Եկեք ավելի սերտ նայենք, թե ինչպես է աշխատում ներդիրների տեսակավորումը:
Ի՞նչ է ներդրման տեսակավորման ալգորիթմը:
Մեկ տարրը միանգամից, ներդրման տեսակավորումը առաջացնում է տեսակավորվող զանգված, որը հաճախ անվանում են ցուցակ:
Օրինակ, տեսակավորումը կիրառվում է բարդ համակարգչային ծրագրերում, ինչպիսիք են կոմպիլյատորները, որտեղ նշանների հերթականությունը կարևոր է ծրագրի մեկնաբանման համար:
Ինչպե՞ս է աշխատում տեղադրման տեսակավորումը:
Երբ մենք օգտագործում ենք ներդիրի տեսակավորումը զանգվածը տեսակավորելու համար, ալգորիթմը սկսվում է ցուցակի ամենափոքր տարրը գտնելով և այն ճիշտ դիրքում տեղադրելով։
Այնուհետև այն գտնում է հաջորդ ամենափոքր տարրը և տեղադրում այն ճիշտ դիրքում և այլն:
Ալգորիթմն աշխատում է՝ պտտելով ցուցակը, յուրաքանչյուր տարրը համեմատելով իր նախորդի հետ:
Եթե տարրերը սխալ հերթականությամբ են, ալգորիթմը դրանք փոխում է: Այնուհետև այն ստուգում է, թե արդյոք ցուցակը տեսակավորված է, և եթե այդպես է, ապա ալգորիթմն ավարտվում է:
Գործնականում ներդրման տեսակավորումը հաճախ իրականացվում է կոդերի մի քանի տողերի միջոցով՝ դարձնելով այն հանրաճանաչ ընտրություն փոքր զանգվածների տեսակավորման համար։ Այնուամենայնիվ, այս ալգորիթմն օգտագործելիս պետք է հաշվի առնել ժամանակի բարդությունը:
Example:
Ահա մի օրինակ, թե ինչպես է աշխատում ներդիրների տեսակավորումը: Մենք կօգտագործենք հետևյալ զանգվածը.
1, 2, 3, 4, 5, 6
Ալգորիթմը սկսվում է՝ գտնելով ցանկի ամենափոքր տարրը, որը 1 է: Այնուհետև այն տեղադրում է ճիշտ դիրքում՝ առաջին դիրքում: Այնուհետև այն գտնում է հաջորդ ամենափոքր տարրը, որը 2 է: Այն տեղադրում է ճիշտ դիրքում, որը երկրորդ դիրքն է:
Այնուհետև այն գտնում է հաջորդ ամենափոքր տարրը, որը 3 է: Այն տեղադրում է ճիշտ դիրքում, որը երրորդ դիրքն է:
Այնուհետև այն գտնում է հաջորդ ամենափոքր տարրը, որը 4 է: Այն տեղադրում է ճիշտ դիրքում, որը չորրորդ դիրքն է և այլն: Ցանկն այժմ տեսակավորված է:
Օրինակից մենք կարող ենք տեսնել, որ ալգորիթմը վեց համեմատություններ և փոխանակումներ է կատարում ցուցակը տեսակավորելու համար: Դա պայմանավորված է նրանով, որ այն տեւում է n2 համեմատություններ և փոխանակումներ՝ n տարրերի ցանկը տեսակավորելու համար: Այս դեպքում n=6:
Ինչպե՞ս բարելավել տեղադրման տեսակավորման ժամանակի բարդությունը:
Մինչ տեղադրման տեսակավորումն ունի O(n2), այն կարող է բարելավվել՝ օգտագործելով ավելի լավ տեսակավորման ալգորիթմ, ինչպիսին է արագ տեսակավորումը։
Quicksort-ն ունի O(n log n) գործարկման ժամանակ, որը շատ ավելի արագ է, քան O(n):2).
Այնուամենայնիվ, որոշ դեպքերում ներդրման տեսակավորումը կարող է ավելի արագ լինել, քան արագ տեսակավորումը:
Օրինակ, եթե ցուցակն արդեն կարգավորված է, ներդիրների տեսակավորումը ավելի քիչ ժամանակ կպահանջի, քան արագ տեսակավորումը:
Գործնականում ներդրման տեսակավորումը հաճախ իրականացվում է կոդերի մի քանի տողերի միջոցով՝ դարձնելով այն հանրաճանաչ ընտրություն փոքր զանգվածների տեսակավորման համար։
Այնուամենայնիվ, այս ալգորիթմն օգտագործելիս պետք է հաշվի առնել ժամանակի բարդությունը:
Ժամանակի բարդություններ
Ամենավատ դեպքի բարդությունը O(n2):
Ժամանակի բարդությունը մեծանում է զանգվածի չափերով: Այն տեւում է n2 համեմատություններ և փոխանակումներ՝ n տարրերի ցանկը տեսակավորելու համար:
Օրինակ, եթե մենք ունենք 1000 չափի զանգված, ապա ալգորիթմը կպահանջի 1,000,000 համեմատություն և փոխանակում զանգվածը տեսակավորելու համար:
Լավագույն գործի բարդությունը O(n):
Ժամանակի բարդությունը նույնն է, ինչ մուտքային զանգվածի չափը: Ի
t վերցնում է n համեմատություն և փոխանակում n տարրի ցուցակը տեսակավորելու համար: Օրինակ, դիտարկեք 5 չափի զանգված: Ալգորիթմը կպահանջի հինգ համեմատություն և փոխանակում զանգվածը տեսակավորելու համար:
Գործի միջին բարդությունը O(n2):
Ժամանակային բարդությունը այս դեպքում վատագույն և լավագույն դեպքերի բարդությունների միջև է:
Այն տեւում է n2 համեմատություններ և փոխանակումներ՝ n տարրերի ցանկը տեսակավորելու համար:
Այսպիսով, ներդրման տեսակավորումը կայուն տեսակավորման ալգորիթմ է։
Ինչու՞ է ներդրման տեսակավորումը կայուն:
Տեղադրման տեսակավորումը կայուն է, քանի որ այն պահպանում է մուտքային զանգվածում հավասար տարրերի կարգը:
Սա կարևոր է բազմաթիվ ծրագրերի համար, ինչպիսիք են տվյալների որոնումը կամ ֆինանսական վերլուծությունը: Օրինակ, եթե մենք ունենք թվերի երկու ցուցակ և ցանկանում ենք համեմատել դրանք, պետք է համոզվենք, որ տարրերի հերթականությունը պահպանված է։
Եթե ցուցակները չտեսակավորվեն, մենք դրանք ճշգրիտ չենք համեմատի։
Թողնել գրառում