Սկիզբ » Ուսումնական նյութեր » Ծրագրավորում » Ծրագրավորման լեզուներ » Assembler » Ալգորիթմական բարդություն և ասիմպտոտիկ վերլուծություն

Ալգորիթմական բարդություն և ասիմպտոտիկ վերլուծություն

| Օգոստոս 17, 2013 | Մեկնաբանված չէ |

Մեքենայական ցիկլ և մեքենայական տակտ կամ ծրագրի կատարման ժամանակային բնութագրերը կապոտի տակից 😉

Ընդհանրապես ցանկացած ծրագիր, անկախ նրանից, թե ինչ պլատֆորմի վրա է աշխատում, օգտագործում է այդ պլատֆորմի ռեսուրսները՝ պրոցեսսորային ժամանակը, օպերատիվ հիշողությունը (օպհ), իսկ որոշ դեպքերում էլ կոշտ սկավառակի հիշողության ռեսուրսները, երբ օպհը զբաղված է և պրոցեսսորը ստիպված է հիշողության ազատ էջեր գտնելու նպատակով ժամանակավորապես կոշտ սկավառակ տեղափոխել օպհ պարունակությունը։

Ցանկացած կենտրոնական պրոցեսսորային սարքավորում (կպս) հրամանների կատարման հաջորդականության ապահովման, սինխրոնիզացման նպատակներով պարունակում է տակտային գեներատոր, որի հիմնական գործառույթը հաստատուն հաճախությամբ որոշակի պարամետրերով ուղղանկյուն իմպուլսների գեներացումն է:

1

Այդ ուղղանկյուն իմպուլսներից յուրաքանչյուրը ունի որոշակի ռեալ ժամանակային տևողություն և դա հաստատուն է տվյալ տակտային գեներատորի գեներացրած բոլոր իմպուսնրի համար և հրամանի կատարման ռեալ տևողությունը չափվում է այդ իմպուլսների քանակի և միավոր իմպուլսի ռեալ տևողության արտադրյալով: Մեկ այդպիսի ուղղանկյուն իմպուլսի տևողությունը կոչվում է մեքենայական տակտ:

Մեքենայական տակտի տևողությունը հակադարձ համեմատական է դրա հաճախությանը, օրինակ եթե ունենք 1 gghzհաճախությամբհամակարգիչ, ապամեկպրոցեսսորայինմիջուկիվրամեկտակտիտևողությունըկկազմի 1/ 1000000000 ≈1* 10^(-9) նանովրկ.

Այսպիսով մեկ մեքենայական հրամանը կատարվում է մեկ և ավելի մեքենայական տակտերի ընթացքում: Օրինակ mult բազմաապտկում գործողությունը՝ կախված կպս տեսակից, կարող է տևել 50 մեքենայական տակտ:

Մեքենայական հրամանները կատարվում են որոշակի ստանդարտ ցիկլի ընթացքում: Մեկ մեքենայական հրամանի կատարման ցիկլը կոչվում է հրամանի կատարման մեքենայական ցիկլԿենտրոնական պրոցեսսորային սարքավորումը (կպս, cpu) մեկ մեքենայական ցիկլի ընթացքում կատարում է հետևյալ գործողությունների հաջորդականությունը.

  1. Հրամանի ընտրում. Կառավարման բլոկը օպհ–ում տեղակայված ծրագրի կոդի սեգմենտից ստանում է հերթական հրամանը, պատճենում է այն կպս –ի ներքին հիշողության մեջ և հրամանների հաշվիչի արժեքը մեծացնում է մեկով, օրինակ եթե պլատֆորմը ունի IA-32 (Intel Architecture) ճարտարապետություն, ապա eip ռեգիստռի արժեքը փոխվում է մեկ հրամանի չափով,

  2. Հրամանի դեկոդավորում. Կառավարման բլոկը որոշում է կատարվող հրամանի տիպը, ուղարկում է այդ հրամանի օպերանդները թվատրամաբանական սարքին (alu) և կատարվող հրամանի տիպին համապատասխան՝ գեներացնում է alu–ի կառավարման էլկտրական իմպուլսներ,

  3. Օպերանդների ընտրում. Եթե հրամանում օգտագործվում է հիշողության մեջ տեղակայված օպերանդ, ապա կառավարման բլոկը գեներացնում է հիշողությունից դրա արժեքի ստացման գործողություն,

  4. Հրամանի կատարում. Alu-ն կատարում է հրամանով նշված գործողությունը, պահում է ստացված արդյունքը նշված տեղում և թարմացնում կառավարող բիթերի (flags) –ի արժեքը, որոնց արժեքի հիման վրա ծրագիրը կարող է որոշել կատարվել է հրմանը, թե ոչ:

  5. Հիշողության մեջ արդյունքի պահպանում (write to memory). Եթե հրամանի կատարման արդյունքը պետք է պահպանվի հիշողության մեջ, ապա կառավարման բլոկը գերացնում է համապատասխան գործողություններ:

Ծրագրի կատարման ժամանակի վերլուծության ընթացքում հնարավոր չէ չանդրադառնալ նաև հիշողությանը դիմելու ժամանակային ծախսերին: Բանը կայանում է նրանում, որ ժամանակակից կպս-ի աշխատանքային արագությունները շատ և շատ անգամ գերազանցում են օպհ աշխատանքային արագություններին: Այդ պատճառով հրամանի կատարամն ժամանակ վերը նշված առաջին փուլի՝ օպերանդի ըտրման ընթացքում համապատասխան տվյալներ ստանալուց առաջ կպս-ը պետք է կատարի մեկ կամ ավելի դատարկ գործողություններ:

2

Հիշողությունից տվյալներ կարդալու mov (նաև ասսեմբլերի հրաման է) գործընթացը բաղակացած է,

  1. ADDR հասցեների կապուղու վրա է դրվում հրամանի օպերանդի բիթերը,

  2. Կպս-ը կառավարման կապուղում տվյալների ընթերցման բիթում (RD) տեղադրում է տրամաբանական ցածր մակարդակ, որը հիշողության կոնտրոլերի համար հանդիսանում հիշողությունից նշված հասցեով տվյալների ընթերցան ազդակ,

  3. Կպս –ը անցնում է տվյալների մուտքի սպասման ռեժիմ, որը տևում է մեկ տակտ: Այդ ընթացքում հիշողության կոնտրոլերը պետք է հասցնի տվյալների կապուղում (DATA) տեղադրել նշված հասցեովհիշողությանբջիջիարժեքը:

  4. ԿպսըRD գծի վրա փոխում է ազդանշանի մակարդակը տրամաբանական ցածրից բարձր և այդ ընթացքում կատարում է տվյալների ընթերցում տվյալների կապուղուց:

Այս ամբողջ գործընթացը սինխրոնիզացվում է տակտային գեներատորի (CLK) ազդանշանների հետին ճակատով՝ երբ տակտը տրամաբանական բարձր մակարդակից անցում է կատարվում տրամաբանական ցածր մակարդակի՝ այսիքն clock –ի posedgeիժամանակ:

Եվ այս ամբողջ 4 տակտից կազմված մեքենայական ցիկլը կատարվում է ընթամենը 32 բիթ կարդալու համար …, քանի-քանի այդպիսի 32 բիթեր է կարդացվում ամբողջ ծրագրային կոդի կատարման ընթացքում, սրան գումարած նաև բազմաթիվ մեքենայական տակտեր տևող այլ մեքենայական հրամանները ու մենք ստանում ենք բավականին պատկառելի մի ժամանակ, որը կպս-ը ծախսում է ամբողջ ծրագրային կոդի կատարման համար: Իսկ հիմա պատկերացնենք, թե որքան կարող ենք օպտիմիզացնել մեր ծրագրերը, որոշ դեպքերում խուսափելով անիմաստ փոփոխականների արժեքներ գրել/կարդալուց ու ժամանակավոր փոփոխականներ օգտագործելուց:
Բայց միևնույն է, օգտագործելով տվյալ պլատֆորմի ու ճարտարապետության համար ամենաքիչ տակտային տևողությամբ ու ամենաօպտիմալ հրամանային համակարգը, միևնույն է չենք կարող կոմպենսացնել վատ գրված ալգորիթմի ժամանակային ծախսը, լավագույն դեպքում, կախված պլատֆորմից, ժամանակային ծախսը կկրճատվի որոշակի C0 հաստատունի չափով, որը զգալի արդյունք չէ:

Ալգորիթմի բարդության հասկացությունը

Ալգորիթմների տեսության մեջ հաճախ օգտագործվում է ալգորիթմի հաշվարկային բարդության հասկացությունը: Ալգորիթմի հաշվարկային բարդությունը ֆունկցիա է, որը ներկայացնում է որոշակի ալգորիթմի կողմից կատարվող աշխատանքի ծավալի ու մուտքային տվյալների չափի միջև կախվածությունը: Ալգորիթմի կատարած աշխատանքի ծավալը բնութագրվում է տարածական և ժամանակային հաշվարկային ռեսուրսներով: Տարածական ռեսուրսը իրենից ներկայացնում է ալգորիթմի կողմից օգտագործվող հիշողության ծավալը, իսկ ժամանակային ռեսուրսը ալգորիթմի կատարման համար անհրաժեշտ տարրական քայլերի քանակով:

Սրանց հիման վրա առանձնացվում են ալգորիթմի տարածական բարդություն և ժամանակային բարդություն հասկացությունները:

Ալգորիթմի տարածական բարդությունը իրենից ներկայացնում է ֆունկցիա, որը բնութագրում է տվյալների չափի և օգտագործվող հիշողության կախվածությունը:

Ալգորիթմի ժամանակային բարդությունը իրենից ներկայացնում է ֆունկցիա, որը բնութագրում է տրված ալգորիթմի տարրական քայլերի կատարման ժամանակային ծախսերը:

Այսպիսով ալգորիթմի հաշվարկային բարդության ֆունկցիայի միջոցով նկարագրվում է ալգորիթմի կողմից օգտագործվող հիշողության ծավալի և կատարման ժամանակի կախվածությունը մուտքային տվյալների չափից:

Հիշողության ծախսերը իրենց սարսափելի չափով զգացնել են տալիս, երբ մենք գործ ունենք միկրոկոնտրոլերների և ընդանհրապես ներդրվող համակարգերի հետ (embedded systems): Օրինակ Atmega8 միկրոկոնտրոլերներն ունի 1 կիլոբայթ օպերատիվ հիշողություն (sram) և այստեղ յուրաքանչյուր հավելյալ օգտագործվող բիթը ոսկու արեժք ունի և այստեղ ալգորիթմի օպտիմալ տարածական բարդությունը կրիտիկական նշանակություն ունի:

Բազմաթիվ ալգորիթմներ կանգնեցնում են երկընտրանքի առջև, երբ պետք է ընտրություն կատարել օգատագործվող հիշողության և ժամանակային ծախսի միջև: Այսպիսի երկընտրանքի տիպիկ օրինակ կարող է հանդիսանալ մեգապոլիսում երկու կետերի միջև կարճագույն ճանապարհի փնտրման ալգորիթմը: Լուծման մի տարբերակն այն է, որ կարելի է նախապես որոշել քաղաքի ցանկացած երկու կետերի միջև կարճագույն հեռավորությունը և արդյունքը պահել հիշողությանմ մեջ, իսկ անհրաժեշտության դեպում, հաշված վայրկյանների ընթացքում ստանալ տրված երկու կետերի միջև հեռավորությունը առանց հաշվարկային ժամանակային ծախսերի: Բայց բավական մեծ քաղաքում կարելի է առանձնացնել միլիոնավոր երկու կետեր և այդ բոլոր առանձնացված երկու կետերը հիշողության մեջ պահելու ծախսերը ահռելի են և փաստորեն հիշողությունը օգտագործվում է չափազանց անարդյունավետ: Այդ պատճառով գործնականում շատ հաճախ ընտրությունը կանգնում է օպտիմալ ժամանակային բարդությամբ ալգորիթմների օգտագործման վրա:

Բնականաբար տարբեր ալգորիթմներ կարող են ունենալ տարբեր ժամանականյին բարդություններ: Օրինակ՝

վերլուծենք insert_sort() սորտավորման ալգորիթմի բարդությունը.

Insertion-Sort(A)

1․ for j -> 2 to length[A]                                   c1, n

2․ do key -> A[j]                                            c2, n - 1

3. ավելացնել A[j] սորտավորված A[1, j - 1] մասին           0,  n -1

4․ i -> j -> 1                                               c4, n - 1

5․ while i > 0 and A[i] > key                                c5, ∑nj = 2 tj

6 do A[i + 1] -> A[i]                                       c6, ∑nj = 2 tj - 1

7 i -> i - 1                                                c7, ∑nj = 2 tj - 1

8 A[i+ 1] key                                               c8, n - 1

Այստեղ c1 c2 … cn հաստատուններ են, որոնք բնութագրում են տարբեր պլատֆորմների վրա ալգորիթմի կատարման առանձնահատկությունները: Օրինակ վերը բերված կոդի 2-րդ տողում կատարվում է n-1 քայլ, բայց տարբեր պլատֆորմների վրա այդ n – 1 քայլը կարող են կատարվել չնչին, բայց և այնպես միմյանցից տարբերվող հաստատուն ժամանակահատվածներում, այդ պատճառով ներմուծվել են cn հաստատունները:

Տվյալ ալգորիթմի համար իդեալական պայման կհանդիսանա մուտքային բազմության սորտավորված լինելը: Այդ դեպքում, երկրորդ ցիկլը ընդանհրապես չի կատարվի

3

և մենք կունենանք գծային բարդություն՝

4

Կամ որ նույնն է, լավագույն դեպքում կունենանք T(n) = O(n) բարդություն:

Եթե մուտքային զանգվածի տարրերը տեղաբաշխված են հակառակ կարգով, ապա այդ դեպքը տվյալ սորտավորման ալգորիթմի համար կհանդիսանա վատագույն պայմանը, քանի որ ալգորիթմը ստիպված պետք է կատարի երկրորդ ցիկլը ամբողջությամբ, այդ դեպքում բարդության հաշվարկը կհանգի.

22

5

որտեղից էլ կստանանք քառակուսային տեսքի արտահայտություն. 

6

Սովորաբար ալգորիթմների վերլուծության ժամանակ, որպես ալգորիթմի բարդության կարգ, դիտարկվում է միայն ֆունկցիայի ամենաարագ աճող հատվածը, մեր դեպքում դեն նետելով գծային մասը, կստանանք․

7

Դեն նետելով նաև a հաստատունը՝ կստանանք վատագույն դեպքում InsertionSort ալգորիթմի բարդությունը .

8

Այսպիսով, ըստ մուտքային տվյալների նախնական տեղաբաշխման, գոյություն ունեն 3 տիպի ալգորիթմական բարդություններ.

  1. Բարդություն վատագույն դեպքում: Գիտենալով այս բարդությունը մենք կարող ենք երաշխավորել, որ տվյալ ալգորիթմը կավարտվի ոչ ուշ քան վատագույն դեպքի ժամանակն է,

  2. բարդություն լավագույն դեպքում: Այս բարդությունը իմացությունը ավելի հաճախ մեզ ոչինչ չի տալիս, քանի որ իրականում տվյալ ալգորիթմի համար իդեալական մուտքային տվյալներ շատ հազվադեպ է հանդիպում:

  3. բարդություն միջին դեպքում: Այս դեպքում ալգորիթմի աշխատանքի ժամանակը բավական մոտ կարող է լինել վատագույն դեպքում բարդության աստիճանին:

Ալգորիթմները կարելի է դասակարգել, ըստ բարդության աստիճանի դասերի, հետևյալ կարգով.

compl

9

Ալգորիթմական բարդության գրաֆիկ

Ալգորիթմների ասիմպտոտիկ վերլուծություն

Θ նշանակում

Եթե g(n) –ը ֆունկցիա է, ապա f(n) = Θ(g(n)) գրառումը նշանակում է, որ գոյություն ունեն այնպիսի c0c1 >0 թվեր և այնպիսի n0 թիվ, որ

0 ≤ c0 g(n) ≤ f(n) ≤ c1 g(n), բոլոր n > n0 թվերի համար:

Եթե f(n) = Θ(g(n)), ապա ասում են g(n) ֆունկցիան հանդիսանում է f(n) ֆունկցիայի համար ասիմպտոտիկ ճշգրիտ գնահատական: Ինչ է սա նշանակում գործնականում: Օրինակ ունենք f(n) = 2x^2 + 7x + 2 ֆունկցիան 

10

Մեզ հետաքրքրում է միայն գրաֆիկի դրական մասը, այսինքն հնարավոր չէ ալգորիթմին տալ բացասական մուտք.

11

և հետևաբար դեն նետելով հաստատուն մասը կարող ենք գրել՝

13

Դժվար չէ նկատել, որ օրինակ n = 3 –ի դեպքում c0  ≤ 13/3 հետևաբար կարող ենք ընտրել այնպիսի c0, որ բավարարվի վերը նշված պայմանը, օրինակ՝  c0 = 5/3, նմանապես կարող ենք ընտրել նաև երկրորդ պայմանի բավարարման համար անհրաժեշտ c1  գործակիցը, օրինակ` 14/3 :

Ընդանհրապես ասիմպտոտիկ վերլուծության դեպքում կարելի է դեն նետել բոլոր հաստատունները և պահել միայն մուտքային արտահայտության ամենաարագ աճող մասը, այսինքն մենք կարող են գրել հետևյալ կերպ՝

14

, այս դեպքում c0 = 1/3 , իսկ c1 = 7/3:

Ինչպես նշել էինք հոդված սկզբում գործակիցների վրա կարող է ազդել այն պլատֆորմը որի վրա աշխատում է տվյալ ալգորիթմը, բայց ինչպիսի հզոր, բազմապրոցեսսորային պլատֆորմ էլ լինի չի կարող ազդել ալգորիթմական բարդության ֆունկցիայի տեսքի վրա՝ սահմանափակվելով միայն հաստատուն գործակիցների արժեքների վրա ունեցած ազդեցությամբ, որը շատ և շատ դեպքերում չնչին է:

Եվ այսպես կերպ ասած Θ(g(n)) –ը ներկայացնում է f(n) ֆունկցիայի պես արագ աճող բոլոր ֆունկցիաների ընտանիքը և f(n) ֆունկցիայի համար հանդիսանում է ալգորիթմական բարդության միաժամանակ և վերին և ներքին սահմանի գնահատման միջոց:

Θ(g(n)) ֆունկցիան կարելի է տրոհել և ներկայացնել երկու ֆունկցիաների տեսքով՝ Ω(g(n)) և Օ(g(n)): Ω(g(n)) –ն արտահայտում է f(n) ֆունկցիայի ալգորիթմական բարդության ներքին սահմանն, իսկ Օ(g(n)) –ը՝ վերին սահմանը: Այսպիսով կարող ենք ձևակերպել. Ասում ենք, որ f(n) = O(g(n)), այն դեպքում, երբ գոյություն ունենք այնպիսի և թվեր, որ բոլոր թվերի համար: Նմանապես Ասում ենք, որ f(n) = Ω (g(n)), այն դեպքում, երբ գոյություն ունենք այնպիսի և թվեր, որ , բոլոր թվերի համար:

Ցանկացած f(n) և g(n) ֆունկցիաների համար տեղի ունի f(n) = Θ(g(n)) արտահայտությունը այն և միայն այն դեպքում, երբ f(n) = O(g(n)) և f(n) = Ω (g(n)): Այսինքն f(n) = Θ(g(n)) գնահատականը կարող է գոյություն ունենալ, այն և միայն այն դեպքում, երբ միաժամանակ գոյություն ունեն f(n) = O(g(n)) և f(n) = Ω (g(n) )գնահատականները և դրանք նույնն են:

Օրինակ, երբ տրված է  f(n) = Ω(n^2), դա նշանակում է, որ տրված ալգորիթմը վատագույն դեպքում չի կարող աշխատել ավելի դանդաղ, քան Ω(n^2) ժամանակում: Իսկ երբ տրված է f(n) = Օ(n^2), դա նշանակում է, որ ամենահաջող մուտքային տվյալների դեպքում անգամ ալգորիթմը չի կարող աշխատել ավելի արագ, քան Օ(n^2) ժամանակն է:

о և ω նշանակումներ

Կարող ենք գրել f(n) = o(g(n)), եթե ,

16

այսինքն f(n) = Ω (g(n)), եթե կամայական ε > 0 համար կգտնվի այնպիսի c0 որ 0≤f(n)≤εg(n), բոլոր n ≥ n0  թվերի համար: Սա նշանակում է, որ գոյություն ունի մի այնպիսի n0  կետ, որ երբ n -> n(n-ը ձգտում է n0), ապա ցանկացած դրական թվի համար կգտնվի մի այնպսի n թիվ n0  թվի շրջակայքից, որ f(n)≤εg(n), իսկ ավելի կարճ ասած գոյություն ունի մի կետ, որից սկսած f(n) ֆունկցիան ձգտում է g(n) ֆունկցիային, բայց չի հասնում, քանի որ g(n) –ը ավելի արագ է աճում: Օրինակ, 2n = o(n^2), բայց ոչ երբեք 2n ≠ o(n^2):

Նմանապես գոյթություն ունի նաև f(n) = ω(g(n)) նշանակումը. f(n) = ω (g(n)), եթե կամայական ε > 0 համար կգտնվի այնպիսի c0 որ, 0≤cg(n)≤εf(n) բոլոր n ≥ n0 թվերի համար: Սա էլ նշանակում է, որ գոյություն ունի, մի կետ, որից սկսած g(n) ֆունկցիան ձգտում է f(n) ֆունկցիային, բայց չի հասնում, քանի որ f(n) –ը ավելի արագ է աճում:

Երկուական փնտրման ալգորիթմի բարդության գնահատում

Շատ հաճախ ալգորիթմների բարդության ներկայացման դեպքում ինկատի են ունենում f(n) = O(g(n)) (մեծատառ O) բարդությունը, այսինքն բարդության վերին սահմանը:

Բերենք երկուական փնտրման ալգորիթմի օրինակը և գնահատենք դրա բարդության վերին սահմանը.

intBinarFind(int* a, intsize, intv)
{

    int temp = 0; //           (1)
    intr = size - 1; //        (2)          
    int m; //                  (3)   
    for(intl = 0; r < size; l <= r)
    {
        m = (l + r)/2;
        if(a[m] == v)
        {
            return l;
        }
        if(a[m] < v)
        {
            l = m + 1;
        }
        if(a[m] > v)
        {
            r = m - 1;
        }
     return-1;
}

Այս ալգորիթմում ամեն մուտքային տվյալների չափը (size) համարենք՝ size = n: Ալգորիթմի յուրաքամչյուր իտերացիայի ժամանակ տեղի է ունենում 0 … n միջակայքի կիսում: Այսպես առաջին իտերացիայի ժամանակ միջակայքը կիսվում է n/2, երկրորդ իտերացիայից հետո կլինի՝ n/4, k – րդ իտերացիայից հետո կունենանք՝ n/(2^m): Վատագույն դեպքում մուտքային բազմության կիսումների քանակը հավասար կլինի հենց բազմության հզորությանը ՝ տարրերի քանակին, այսինքն n = 2^m <=> m = logn, այսինքն երկուական փնտրման ալգորիթմի ալգորիթմական բարդությունն է O(logn): (1), (2), (3) տողերի բարդությունը O(1) է կամ հաստատուն ժամանակ:

Ալգորիթմի բարդությունը մի քանի կոնստրուկցիաների դեպքում

  1. Line1 O(1)
    Line2 O(1)
    ................
    ................
    Linen O(1)

     

Եթե հասարակ տողեր են և կախված չեն մուտքային տվյալերի չափից ,ապա դեպքում ալգորիթմի բարդութունը O(1).

  1. If(.......)
    {
            ..........
    }
    else
    {
            ..........
    }

Եթե if() else () բլոկներում կատարվում է O(N) բարդությամբ գործողություններ, ապա ալգորիթմի բարդութունը O(N) է, եթե հասարակ տողեր են և կախված չեն մուտքային տվյալերի չափից ,ապա դեպքում ալգորիթմի բարդութունը O(1):

  1. for(int i = 0; i < n; ++i)
    {
            .............
    }

Այս դեպքում ակնհայտ է, որ ալգորիթմը կախված է մուտքային տվյալների չափից և կկատարվի n անգամ, ուստի բարդությունը կլինի՝

O(n):

  1. for(int i = 0; i < n; ++i)
    {
           for(int j = 0; j < n; ++j)
          {
                .............
          }
    }

Այս դեպքում արտաքին ցիկլի յուրաքանչյուր իտերացիայի համար ներքին ցիկլը կկատարվի ոչ պակաս քան n անգամ՝ k ≤ n, ուստի կստանանք O(k*n) կամ՝ O(n*n) = O(n^2):

ՕԳՏԱԳՈՐԾՎԱԾ ԳՐԱԿԱՆՈՒԹՅԱՆ ՑԱՆԿ

1. Kip Irvine, Assembly Language for x86 Processors,
2. Thomas H. Cormen, Introduction to algorithms,
3. Асимптотический анализ алгоритмов, http://habrahabr.ru/post/78728/,
4. Оценка сложности алгоритмов, http://habrahabr.ru/post/104219/,
5. Вычислительная сложность, https://ru.wikipedia.org/wiki/%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D1%82%D0%B5%D0%BB%D1%8C%D0%BD%D0%B0%D1%8F_%D1%81%D0%BB%D0%BE%D0%B6%D0%BD%D0%BE%D1%81%D1%82%D1%8C#.D0.92.D1.80.D0.B5.D0.BC.D0.B5.D0.BD.D0.BD.D0.B0.D1.8F_.D0.B8_.D0.BF.D1.80.D0.BE.D1.81.D1.82.D1.80.D0.B0.D0.BD.D1.81.D1.82.D0.B2.D0.B5.D0.BD.D0.BD.D0.B0.D1.8F_.D1.81.D0.BB.D0.BE.D0.B6.D0.BD.D0.BE.D1.81.D1.82.D0.B8,
6. «O» большое и «o» малое, https://ru.wikipedia.org/wiki/%C2%ABO%C2%BB_%D0%B1%D0%BE%D0%BB%D1%8C%D1%88%D0%BE%D0%B5_%D0%B8_%C2%ABo%C2%BB_%D0%BC%D0%B0%D0%BB%D0%BE%D0%B5#.D0.9E.D0.BF.D1.80.D0.B5.D0.B4.D0.B5.D0.BB.D0.B5.D0.BD.D0.B8.D1.8F:
Ալգորիթմական բարդություն և ասիմպտոտիկ վերլուծություն, 10.0 out of 10 based on 12 ratings

Նշագրեր: , , , ,

Բաժին: Assembler, C և C++, Ալգորիթմներ, Ծրագրավորում

Կիսվել , տարածել , պահպանել

VN:F [1.9.20_1166]
Rating: 10.0/10 (12 votes cast)

Մեկնաբանեք

Կհաստատվեն միայն մեսրոպատառ հայերենով գրած մեկնաբանությունները

257