Алгоритмы и их сложности



Download 443,07 Kb.
Sana04.06.2022
Hajmi443,07 Kb.
#636217
Bog'liq
4-алгоритма-критерии10уз


Алгоритмик лойихаларни бахолаш меёрлари
Алгоритм мураккаблиги тахлили
Алгоритм мураккаблигини тахлил қилишдан мақсад берилган масалани энг оптимал ечими алгоритмини топишдан иборат.
Оптимал алгоритм
Min
Хотира
Min
Вақт
Тариф 1. Мураккаблик назарияси, хисоблашлар назарияси қисми бўлиб, қўйилган муаммони хал қилиш учун сарфланадиган ресурслар ёки хисоблашлар нархини тахлил қилиш билан шугилланади.
Тариф 2. Алгоритм хисоблаш мураккаблиги — қандайдир алгоритм томонидан бажариладиган ишлар хажмини кирувчи маълумотларга боглиқлигини аниқловчи функциядир.
Иш хажми хисоблаш ресурслари деб аталувчи замон ва макон абстракт параметрлари билан ўлчанади.
Вақт муаммони ечиш учун зарур бўлган элементар қадамлар билан аниқланади, макон маълумотлар сақланувчи хотира қурилмаси катталиги билан аниқланади.
Алгоритмларни лойихалашдаги марказий савол «бажариш тезлиги ва банд қилинган хотира катталиги кириш ва чиқишга боглиқ қандай ўзгаради » деган саволдир.
Мураккаблик даражалари
констант;
– логарифмик;
– чизиқли;
- полиноминал (квадрат, кубик …);
– экспоненциал;
факториал
Бу f(n) = O(g(n)) ёзув, f(n) функция g(n) функциядан секинроқ ўсишини кўрсатади.
Бундай O бахо алгоритмни вақтга боглиқ мураккаблигини юқори чегарасини белгилайди – асимптотик мураккаблик дейилади.
Алгоритмик мураккабликларни амалий бахолаш мулохазалари
  • Вақт ва фойдаланилаётган хотира бўйича мураккаблик;
  • Ечимга қўйиладиган талаблар;
  • Алгоритмни реализация ва отладка қилиш мураккаблиги;
  • Мураккаблик белгиси ифодада константа қиймати
  • Ўрта ва ёмон бахоланувчи алгоритмларни бажарилиши.



Алгоритмлар мураккаблигини бахолашга мисоллар
Масала 1. n – тартибли Фибоначчи сонини хисоблаб топинг (полиномиал мураккаблик):
Алгоритм 1.1
  • Рекурсив «охиридан» хисоблаймиз (…);
  • Алгоритм бажарилиши мураккаблиги

  • double FibFunc(int IndexNumber)//Функцияга сон берилади
    {
    // Шарт текширилади 1 ёки 2 сонга борилдими
    if (IndexNumber == 1 || IndexNumber == 2)
    return 1.0; // Ха бўлса 1 қайтарамиз
    else
    return (FibFunc(IndexNumber - 1) + FibFunc(IndexNumber - 2));
    // Йўқ бўлса рекурсив яна ўзини чақирамиз
    }


Функцияга мурожаатлар сони


Сон тартиби

Фибоначчи
сони

Функцияга мурожаат
сони

1

1

1

2

1

1

3

2

3

4

3

5

5

5

9

6

8

15

7

13

25

8

21

41

9

34

67

Алгоритм 1.2
  • Дастлаб циклда «бошидан» (…) ни хисоблаймиз;

  • Алгоритм бажарилиши мураккаблиги (чизиқли)

  • double FibFunc(int IndexNumber)
    {
    double f1, f2, f3; //Ўзгарувчилар эълон қилиш
    f1 = f2 = 1.0; // 1- ва 2- сонларни аниқлаймиз
    f3 = 0.0;
    int i = 3; //Қадам аниқланади
    while (i <= IndexNumber) //Берилган номерга етгунча
    {
    f3 = f2 + f1; // Формуладан i-сонни топамиз
    //Навбатдаги қадам учун ўзгарувчилар алмаштирилади
    f1 = f2; //f2 ўтади f1 га
    f2 = f3; //f3 ўтади f2 га
    i = i + 1; //Қадам бирга ортади
    }
    return f3; //Охирида топилган сон қайтарилади
    }

Масала 2. Хисобланг :
Алгоритм 2.1 (чизиқли мураккаблик)
  • Циклда хисоблаймиз ;
  • Алгоритм бажарилиши мураккаблиги

  • Алгоритм 1.2 (логарифмик мураккаблик)
  • Хисоблашда алмаштиришдан фойдаланамиз
  • Алгоритм бажарилиши мураккаблиги


  • long mypow(long a, long k)
    { long b = 1;
    while (k !=0 )
    {
    if (k % 2 == 0)
    {k /= 2; a *= a;}
    else
    {k--; b *= a;}
    }
    return b;
    }

Итерациялар сони


Даража

Итерация
сони

1

1

2

2

3

3

4

3

5

4

6

4

7

5

8

4

9

5

10

5

11

6

12

5

13

6

14

6

Download 443,07 Kb.

Do'stlaringiz bilan baham:




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish