Սա մի հարց է, որը ես բազմիցս քննարկել եմ իմ մտքում և վստահ եմ, որ սա այն հարցն է, որը կարող է ունենալ նաև ձեզանից մի քանիսը: Փորձեմ պարզել, թե ինչու պետք է սովորեք տվյալների կառուցվածքները (DS) և ալգորիթմը:
Տվյալների կառուցվածքն ու ալգորիթմե՞րը: Ի՞նչ են դրանք
Տվյալների կառուցվածքներըինչպես ասում է անունը, տվյալների պահպանման կառուցվածք է: Տվյալների հիմնական տեսակներն են՝ զանգված, ցուցակ, կույտ, հերթ, քարտեզ, կույտ… և այլն:
Ալգորիթմները խնդրի լուծման տարբեր եղանակներ են: Օրինակ, թե ինչպես կարելի է տեսակավորել իրերի ցանկը, ինչպես գտնել տարր… և այլն:
Լավ, ինչո՞ւ են դրանք կարևոր:
«Դուք չեք կարող մեծ շենքեր կառուցել թույլ հիմքի վրա». Դիտարկեք DS-ը և Ալգորիթմը որպես ցանկացած հիանալի ծրագրակազմ ստեղծելու հիմք:
Բոլոր հիմնական DS-ը և ալգորիթմներն արդեն ներկառուցված են ձեզ համար ծրագրավորման լեզուների գրադարանների մեծ մասում: Նրանք գոյություն ունեն մի պատճառով. Դուք կարող եք լուծել խնդիրը արդյունավետ/օպտիմիզացված եղանակով, երբ գիտեք կիրառվող DS կամ Ալգորիթմը: Հատկապես, երբ դուք կառուցում եք ծրագրակազմ, որը պետք է մշակի տվյալների մեծ ծավալ, ճիշտ DS և Ալգորիթմի ընտրությունը մեծ նշանակություն ունի դրա մասշտաբի համար:
Ստորև բերված են մի քանի օրինակներ՝ նպատակը լուսաբանելու համար:
Ենթադրենք, որ դուք պետք է տեսակավորեք 1 միլիոն գրառումների ցանկը: Ինչպե՞ս ես դա անում:
Ցուցակը տեսակավորելու տարբեր եղանակներ կան, հետևաբար նաև մի քանի տեսակավորման ալգորիթմներ: Օրինակ, եթե դուք օգտագործում եք «պղպջակային տեսակավորում» մոտեցումը, դրա տեսակավորման համար պահանջվում է O(n*n) ժամանակ, մինչդեռ «միաձուլման տեսակավորումը» կարող է նույն տեսակավորումը կատարել O(n log n) ժամանակում:
Այսպիսով, «միաձուլման տեսակավորումը» շատ ավելի լավ կգործի «փուչիկների տեսակավորման» մոտեցման համեմատ, երբ n-ի արժեքը բարձր է:
Ինչպե՞ս եք փնտրում տարր 1 միլիոն գրառումների ցանկից:
Եթե դուք կրկնում եք ցուցակի վրա և որոնում եք որևէ տարր, կարող եք դա անել O(n) ժամանակում, բայց եթե օգտագործում եք երկուական որոնում մոտեցումը, կարող եք դա անել O(log n) տարբերակով:
n-ի ավելի բարձր արժեքը, երկուական որոնումը շատ ավելի լավ կաշխատի:
Գիտե՞ք, որ երբ դուք ստեղծում եք տվյալների բազայի ինդեքս՝ ձեր հարցումն ավելի արագ դարձնելու համար, այն օգտագործում է երկուական որոնումը ներքին:
Ենթադրենք, դուք ունեք 1 միլիոն իրերի հավաքածու, և դուք պետք է զտեք հավաքածուից մի քանի հազար իրեր: Ենթադրենք, որ հավաքածուների իրերը եզակի են։ Ինչպե՞ս ես դա անում:
Ուղղակի մոտեցումը կլինի երկու օղակների օգտագործումը: Արտաքին օղակը կկրկնվի ավելի քան միլիոն տարրեր, իսկ ներքին օղակը կկրկնվի 1000 տարրերի վրա, և դուք ունեք պայման՝ զտելու համապատասխան տարրերը: Այս մոտեցման ժամանակային բարդությունը կլինի O(m * n): Կարո՞ղ ենք դա պարզեցնել:
Քանի որ տարրերը եզակի են, այստեղ կարող եք օգտագործել հեշ հավաքածու՝ 1 միլիոն տարրերը պահելու համար: Այնուհետև կարող եք զտել մեր տարրերը O(n) անգամ: Դա պայմանավորված է նրանով, որ դուք կարող եք որոնել տարր հեշ հավաքածուում O(1) ժամանակում:
Ինչ տեսակի ցուցակ կօգտագործեիք, երբ ցանկանում եք կատարել բազմաթիվ ներդիր/ջնջման գործողություններ ցանկում:
Եթե տեղադրման/ջնջման գործողությունները չկատարվեն ցանկի վերջում, կապված ցուցակը ավելի լավ կաշխատի, քան զանգվածների ցուցակը: Ինչո՞ւ։ Զանգվածների ցանկի պատահական ինդեքսի վրա տեղադրումը/ջնջումը միջինում տևում է O(n) ժամանակ, մինչդեռ կապակցված ցուցակը միայն O(1) ժամանակ է պահանջում:
Ձեզ անհրաժեշտ է տվյալների պահեստ՝ առանցքային արժեքների զույգերով, բայց պատվերով: Ինչպե՞ս ես դա անում:
Այստեղ կարող եք օգտագործել ծառի քարտեզ: Բայց զետեղել/ջնջել/որոնում գործողությունների համար պահանջվում է O(log n) ժամանակ, քանի որ այն պահուստավորվում է AVL կամ կարմիր սև ծառով:
Գիտե՞ք, թե ինչպես է Google Maps-ը գտնում օպտիմալ ճանապարհը ծագման և նպատակակետի միջև:
Սա գրաֆիկի խնդիր է, այնպես չէ՞: Ինչպե՞ս եք անցնում գրաֆիկի երկու հանգույցների միջև: Ինչպե՞ս եք գտնում կարճ ճանապարհը: Նմանատիպ խնդիրներ լուծելու համար հայտնի են գրաֆիկական ալգորիթմներ:
Դժվա՞ր է այս ամենը սովորելը:
Աշխատանքի ընթացքում դուք ստանում եք բոլոր հիմնական DS-ն ու ալգորիթմները անվճար՝ որպես ժամանակակից ծրագրավորման լեզուների գրադարանների մաս: Տարբեր DS-ի և ալգորիթմների առանձնահատկություններին (գործողությունները, ժամանակի և տարածության բարդությունները) տեղյակ լինելն այն ամենն է, ինչ ձեզ հարկավոր է ձեր լուծումը ստեղծելու համար: Նաև շատ դեպքերում դուք պետք է դրանք միասին կազմեք՝ որոշակի խնդիր լուծելու համար: Երբ խնդիր է տրվում, նախ մտածեք այն լուծելու հնարավոր լավագույն DS/ալգորիթմի մասին և ժամանակի ընթացքում կտեսնեք, որ դուք տիրապետում եք այդ հմտությանը:
Մեկ այլ պատճառ, որ դուք կարող եք դրանք սովորել, այն է, որ աշխատանքի ընդունվելիս աշխարհի բոլոր բարձրակարգ տեխնոլոգիական ընկերությունները փորձարկում են ձեզ այս հիմնադրամի հայեցակարգերի վրա: Ո՞վ չի ցանկանում աշխատել այս առաջատար ընկերություններում: :) այնպես որ դուք ավելի լավ է սովորեք դրանք:
Եզրակացություն
Տվյալների կառուցվածքները և ալգորիթմները սովորելը օգնում է ձեզ արդյունավետ լուծումներ գտնել խնդրին և, հետևաբար, օգնում է ձեզ դառնալ լավ ծրագրավորող:
