site logo
  • Կայքի մասին
  • Ծրագրավորում
  • Ժեշտ
  • Անվտանգություն
  • Հարց ու Պատասխան (ՀուՊ)
Օգոստոս 17, 2013  |  By Neutrino In

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

complexity

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

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

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

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 հաստատունը՝ կստանանք վատագույն դեպքում Insertion–Sort ալգորիթմի բարդությունը .

8

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

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

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

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

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

compl

9

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

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

Θ նշանակում

Եթե g(n) –ը ֆունկցիա է, ապա f(n) = Θ(g(n)) գրառումը նշանակում է, որ գոյություն ունեն այնպիսի c0, c1 >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 -> n0 (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++ Ալգորիթմներ ալգորիթմների բարդության վերլուծություն ասիմպտոտիկ անալիզ երկուական փնտրում Ծրագրավորում մեքենայական ցիկլ/տակտ
Previous StoryԱղվես դաս 3: պարզ օրինակներ և շարժ բլոկը [տեսանյութ]
Next StoryՍտանում ենք ծանուցում սեփական համարին, անվճար sms հաղորդագրության տեսքով linux օհ-ից։

Comments: no replies

Join in: leave your comment Cancel Reply

(will not be shared)

Որոնում

Նշագրեր

*Nix-եր (18) android (17) C++ (19) C և C++ (27) Excel (10) html (10) Network Administration (16) System Administration (28) Windows 7 (14) Ալգորիթմներ (15) Անվտանգություն (29) ԳՆՈՒ/Լինուքս (16) Թեյնիկներին (57) Ժեշտ (44) Լակոնիկ (21) Լինուքս/Յունիքս հրամաններ (29) Լուսանկարչություն և մշակում (15) Խելախոսներ (19) Ծրագրավորման լեզուներ (16) Ծրագրավորում (64) Ծրագրեր (48) Հայականացում (28) Հումոր (11) Ուսումնական նյութեր (34) Սոցցանցային Հմտություններ (19) Վեբ (25) Վերլուծություն (10) Վորդպրես (21) ՏՏ և փիլիսոփայություն (21) Տվյալների բազաներ (12) Օպերացիոն համակարգեր (27) Օֆիսային ծրագրեր (22) անդրոիդ (16) բաշ (10) ինտերնետ (11) խելախոսներ (13) համացանց (15) հայատառ (10) հայերեն (11) հայերեն ստեղնաշար (11) հայկական սոֆթ (11) ստեղնաշար (10) սքրիփթ (14) վինդոուս (12) տեսանյութ (23)
Copyright ©2017 ThemeFuse. All Rights Reserved