Kirish Asosiy qism Chiziqli algoritmlar

Algoritm turlari
Hеch qanday shart tеkshirilmaydigan va faqat oldindan belgilangan tartib bilan kеtma – kеt bajariladigan jarayonlarni kuzatish mumkin. Bunday mazmundagi algoritmlar chiziqli algoritmlar dеb yuritiladi.

lgoritm muayyan muammoni hal qilish uchun mo'ljallangan qadamlar ketma-ketligi. Boshqacha aytganda, algoritm bu muammoni hal qilishning bir usuli hisoblanadi. Ushbu sifatda algoritm har qanday, shu jumladan kundalik vazifalarni hal qilish usulini ko'rsatish uchun ishlatiladi. Ammo bu holda biz kompyuter hisoblash algoritmlari haqida gapiramiz.

"Algoritm" atamasi fars matematigi al-Xorazmiy nomidan kelib chiqqan bo'lib, uning asarlari matematika fan sifatida shakllanishida muhim rol o'ynagan.

Algoritm hisob-kitoblarni amalga oshiradigan kirish ma'lumotlariga ega bo'lishi mumkin, shuningdek, chiqish natijasi bo'lishi mumkin - bitta qiymat yoki qiymatlar to'plami. Aslida, algoritmning vazifasi kirish qiymatlarini hafta oxiri aylantirishdan iborat.

Algoritmning muhim mezonlari samaradorlikdir. Algoritm muammoni mukammal hal qilishi mumkin, ammo samarali bo'lmasligi mumkin. Qoida tariqasida, algoritmning samaradorligi bu algoritm bajarilishi kerak bo'lgan vaqtni anglatadi.

Dasturning umumiy vaqti ikki omilga bog'liq:

har bir operatorning ish vaqti

har bir operatorning ishlash chastotasi

Har bir operatorning bajarilishi vaqti ish vaqti, operatsion tizim va boshqa tizim xususiyatlariga bog'liq.

Samaradorligini qarab algoritmlar ko'p turlari bor, algoritmlar quyidagi turlarini ajratish mumkin, shu jumladan, (samaradorligini kamaytirish maqsadida keltirilgan):

Ilova doimiy vaqtni talab qiladigan operatsiyalarning qat'iy miqdorini amalga oshiradi.

Masalan, quyidagi operatsiyalar to'plami:

int x = 10;

if(x > 0)

{

x--;

}

else

{

x++;

}

Logaritmik (kirish)

Doimiy vaqt dasturlari bilan sekinroq amalga oshiriladi. Bunday algoritmning misoli ikkilik qidiruv algoritmi bo'lishi mumkin.

public static int Rank(int key, int[] numbers)

{

int low = 0;

int high = numbers.Length - 1;

while (low <= high)

{

// o'rtasini toping

int mid = low + (high - low) / 2;

// agar qidiruv tugmasi o'rtacha qiymatdan kamroq bo'lsa

// keyin yuqori chegara o'rtadagi element bo'ladi

if (key < numbers[mid]) high = mid - 1;

else if (key > numbers[mid]) low = mid + 1;

else return mid;

}

return -1;

}

Misol uchun, agar numbers bir qator biz bor bo'lsa 8 elementlar, keyin kerakli ob'ektni topish, biz izchil elementlar sonini ajratish kerak 2. Ya'ni, kerakli elementni topish uchun biz 3 tsiklini bajarishimiz kerak. Va bu natija logaritmik funktsiya bilan tavsiflanadi: log28 = 3;

N ning o'sishi bilan ishlash vaqtining o'sishi bir necha doimiy qiymat bilan ortadi.

Chiziqli (N)

Odatda, bu usul tsiklga asoslangan joyda topiladi. Misol uchun, faktorial funktsiyasi:

private static int Factorial(int n)

{

int result = 1;

for(int i=1; i<=n; i++)

{ result *= i;

}

return result;

}

Bu erda usulning bajarilishi n ga bog'liq. n uchun qanday qiymat usulga o'tkaziladi, ko'p marta va tsikl amalga oshiriladi. Ya'ni, ushbu usul uchun algoritmning mehnat intensivligining o'sishi n qiymatiga mutanosib, shuning uchun u lineer deb ataladi.

Chiziqli-logaritmik (NlogN)

Bunday algoritm bir misol birlashish tartiblash (birlashtirish sort) sifatida xizmat qilishi mumkin)

Kvadrat (N2)

Qoida tariqasida, usullari, bu algoritm mos, ikki ko'chadan o'z ichiga oladi - tashqi va ichki, barcha qadriyatlar uchun amalga oshiriladi qadar N. misol sifatida, biz bir qabariq saralash dasturi (bubble sort) n elementlar qator, qaysi eng yomon holatda, biz ikki ko'chadan yordamida n*n elementlarni chetlab qilish kerak:

private static void BubbleSort(int[] nums)

{

int temp;

for (int i = 0; i < nums.Length - 1; i++)

{

for (int j = i + 1; j < nums.Length; j++)

{

if (nums[i] > nums[j])

{

temp = nums[i];

nums[i] = nums[j];

nums[j] = temp;

} } } }

Ushbu algoritmga mos keladigan dasturlarda uchta tsikl ishlatiladi, masalan:

char[] chars = new char[] { 'A', 'B', 'C' };

for(int i=0; i

{

for(int j=0; j

{

for(int k=0; k

{

Console.WriteLine($"{chars[i]}{chars[j]}{chars[k]}");

}

}

}

Biroq turmushda uchraydigan juda ko’pgina jarayonlar esa shartlar asosida boshqariladi, ular tarmoqlanuvchi yoki takrorlanuvchi xususiyatga egadirlar.

Shartga muvofiq bajariladigan ko’rsatmalar bilan tuziladigan algoritmlar tarmoqlanuvchi algoritmlar dеyiladi. Bunday algoritmlar bilan biz har kuni duch kеlamiz. Ko’chadan o’tishimiz svetoforning yongan chirog’i rangiga,ko’chaga qanday kiyimda chiqishimiz ob- havoga, elеktr jihozini ishlatishimiz uning qanday kuchlanishli manba’ga ulashimizga bog’liqdir.