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

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

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

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

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

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

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

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

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

^{Հրամանի ընտրում}^{. Կառավարման բլոկը օպհ–ում տեղակայված ծրագրի կոդի սեգմենտից ստանում է հերթական հրամանը, պատճենում է այն կպս –ի ներքին հիշողության մեջ և հրամանների հաշվիչի արժեքը մեծացնում է մեկով, օրինակ եթե պլատֆորմը ունի}^IA-32⁽Intel Architecture^{) ճարտարապետություն, ապա}^eip^{ռեգիստռի արժեքը փոխվում է մեկ հրամանի չափով,}
^{Հրամանի դեկոդավորում}^{. Կառավարման բլոկը որոշում է կատարվող հրամանի տիպը, ուղարկում է այդ հրամանի օպերանդները թվատրամաբանական սարքին (}^alu^{) և կատարվող հրամանի տիպին համապատասխան՝ գեներացնում է alu–ի կառավարման էլկտրական իմպուլսներ,}
^{Օպերանդների ընտրում}^{. Եթե հրամանում օգտագործվում է հիշողության մեջ տեղակայված օպերանդ, ապա կառավարման բլոկը գեներացնում է հիշողությունից դրա արժեքի ստացման գործողություն,}
^{Հրամանի կատարում}^.^Alu^{-ն կատարում է հրամանով նշված գործողությունը, պահում է ստացված արդյունքը նշված տեղում և թարմացնում կառավարող բիթերի (flags) –ի արժեքը, որոնց արժեքի հիման վրա ծրագիրը կարող է որոշել կատարվել է հրմանը, թե ոչ:}
^{Հիշողության մեջ արդյունքի պահպանում}^{(write to memory). Եթե հրամանի կատարման արդյունքը պետք է պահպանվի հիշողության մեջ, ապա կառավարման բլոկը գերացնում է համապատասխան գործողություններ:}

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

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

^ADDR^հ^{ասցեների}^{կապուղու}^վրա^է^դրվում^{հրամանի օպերանդի բիթերը,}
^{Կպս-ը կառավարման կապուղում տվյալների ընթերցման}^բիթում⁽^RD^{) տեղադրում է տրամաբանական ցածր մակարդակ, որը հիշողության կոնտրոլերի համար հանդիսանում}^{հիշողությունից նշված հասցեով տվյալների ընթերցան ազդակ}^,
^{Կպս –ը անցնում է տվյալների մուտքի սպասման ռեժիմ, որը տևում է մեկ տակտ: Այդ ընթացքում հիշողության կոնտրոլերը պետք է հասցնի տվյալների կապուղում}⁽^DATA⁾^{տեղադրել նշված}^{հասցեով}^{հիշողության}^բջիջի^արժեքը^:
^Կպս^–^ը^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

^{Այստեղ c}₁^c_{2 …}^c_n^{հաստատուններ են, որոնք բնութագրում են տարբեր պլատֆորմների վրա ալգորիթմի կատարման առանձնահատկությունները: Օրինակ վերը բերված կոդի 2-րդ տողում կատարվում է n-1 քայլ, բայց տարբեր պլատֆորմների վրա այդ n – 1 քայլը կարող են կատարվել չնչին, բայց և այնպես միմյանցից տարբերվող հաստատուն ժամանակահատվածներում, այդ պատճառով ներմուծվել են c}_n^{հաստատունները:}

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

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

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

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

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

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

^Դեն^{նետելով}^նաև^a^{հաստատունը՝}^{կստանանք վատագույն դեպքում}^Insertion^–^Sort^{ալգորիթմի բարդությունը .}

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

^{Բարդություն վատագույն դեպքում: Գիտենալով այս բարդությունը մենք կարող ենք երաշխավորել, որ տվյալ ալգորիթմը կավարտվի ոչ ուշ քան վատագույն դեպքի ժամանակն է,}
^{բարդություն լավագույն դեպքում: Այս բարդությունը իմացությունը ավելի հաճախ մեզ ոչինչ չի տալիս, քանի որ իրականում տվյալ ալգորիթմի համար իդեալական մուտքային տվյալներ շատ հազվադեպ է հանդիպում:}
^{բարդություն միջին դեպքում: Այս դեպքում ալգորիթմի աշխատանքի ժամանակը բավական մոտ կարող է լինել վատագույն դեպքում բարդության աստիճանին:}

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

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

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

^{Θ նշանակում}

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

^{0 ≤ c}₀^{g(n) ≤ f(n) ≤ c}₁^{g(n), բոլոր n > n}₀^{թվերի համար:}

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

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

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

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

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

^{, ա}^{յս դեպքում ^c₀ = 1/3}^{, իսկ ^c₁ = 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)), եթե}^,

^{այսինքն f(n) =}^Ω^{(g(n)), եթե կամայական ε > 0 համար կգտնվի այնպիսի ^c₀}^{որ 0≤f(n)≤εg(n)}^{, բոլոր ^{n ≥ n}₀}^{թվերի համար: Սա նշանակում է, որ գոյություն ունի մի այնպիսի ⁿ₀}^{կետ, որ երբ n -> ⁿ₀}^{(n-ը ձգտում է ⁿ₀}^{), ապա ցանկացած}^{դրական թվի համար կգտնվի մի այնպսի n թիվ ⁿ₀}^{թվի շրջակայքից, որ 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 համար կգտնվի այնպիսի ^c₀}^որ^{, 0≤cg(n)≤εf(n) բոլոր ^{n ≥ n}₀}^{թվերի համար: Սա էլ նշանակում է, որ գոյություն ունի, մի կետ, որից սկսած 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) է}^կամ^{հաստատուն}^{ժամանակ}^:

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

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

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

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

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

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

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

^O(n):

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:

Նշագրեր: featured, ալգորիթմների բարդության վերլուծություն, ասիմպտոտիկ անալիզ, երկուական փնտրում, մեքենայական ցիկլ/տակտ

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

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

Գնահատել

Rating: 10.0/10 (12 votes cast)

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

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

Գնահատել

Մեկնաբանեք

Հեղինակ ՝ Neutrino
(Հեղինակի էջը)

ՀուՊ (Հարց ու Պատասխան, ֆորում)

Վերջին նյութերը

Բաժիններ

Գնահատվածները (անցյալ 7 օրվա ընթացքում)

Ֆեյսբուք և Գ+

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

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

Գնահատել

Թեմատիկ նյութեր

Բաժանորդագրվել

Մեկնաբանեք

Հեղինակ ՝ Neutrino (Հեղինակի էջը)

ՀուՊ (Հարց ու Պատասխան, ֆորում)

Վերջին նյութերը

Բաժիններ

Գնահատվածները (անցյալ 7 օրվա ընթացքում)

Ֆեյսբուք և Գ+

Հեղինակ ՝ Neutrino
(Հեղինակի էջը)