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

Алгоритмик лойихаларни бахолаш меёрлари
Алгоритм мураккаблиги тахлили
Алгоритм мураккаблигини тахлил қилишдан мақсад берилган масалани энг оптимал ечими алгоритмини топишдан иборат.
Оптимал алгоритм
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