Algorithm

Algorithm — muammoni yechish yoki aniq natijaga erishish uchun bajariladigan tartibli va chekli ko‘rsatmalar ketma-ketligi.

Algorithm faqat dastur kodi emas. U masalani qanday yechish kerakligini til va platformadan mustaqil ravishda ifodalaydi.

Bir algorithm Python, JavaScript, C++ yoki boshqa tilda implementatsiya qilinishi mumkin.

Asosiy xususiyatlar

Yaxshi aniqlangan algorithm odatda quyidagi xususiyatlarga ega:

kirish ma’lumoti;
chiqish natijasi;
aniqlik;
chekli qadamlar;
bajariluvchan amallar;
to‘g‘rilik;
umumiy holatlar uchun qo‘llanish.

Kirish va chiqish

Algorithm nol yoki undan ko‘p input qabul qiladi.

Misol: ikki sonning kattasini topish.

Input:

A, B

Output:

max(A, B)

Input cheklovlari algorithm tanloviga ta’sir qiladi.

Aniqlik

Har qadam tushunarli va bir ma’noli bo‘lishi kerak.

“Qiymatni biroz oshir” noaniq.

“Qiymatga 1 qo‘sh” aniq.

Dastur kompyuter bajarishi uchun har amal formal ma’noga ega bo‘ladi.

Cheklilik

Algorithm ma’lum shartda tugashi kerak.

Cheksiz loop muammo yechimi bo‘lmasa, algorithm talabi bajarilmaydi.

Ba’zi server va operating system processlari ataylab doimiy ishlaydi, ammo ular ichidagi har request algorithm’i tugallanuvchi bo‘lishi mumkin.

To‘g‘rilik

Algorithm barcha ruxsat etilgan inputlar uchun talab qilingan natijani qaytarsa to‘g‘ri hisoblanadi.

Faqat bir nechta testdan o‘tish matematik to‘g‘rilik isboti emas.

To‘g‘rilik:

invariant;
induction;
contradiction;
precondition va postcondition

orqali asoslanishi mumkin.

Pseudocode

Algorithm dasturlash tiliga bog‘lanmagan pseudocode bilan yozilishi mumkin.

Misol:

FUNCTION maximum(A, B)
    IF A > B
        RETURN A
    ELSE
        RETURN B

Pseudocode syntaxdan ko‘ra mantiqqa e’tibor beradi.

Flowchart

Algorithm diagramma orqali ham ifodalanadi.

Belgilar:

boshlanish/yakun;
amal;
shart;
input/output;
yo‘nalish.

Murakkab algorithm uchun flowchart juda katta bo‘lishi mumkin. Matnli pseudocode versiya boshqaruviga qulayroq.

Sequential algorithm

Qadamlar ketma-ket bajariladi.

Misol:

sonni o‘qish;
2ga ko‘paytirish;
natijani chiqarish.

Branching

Shartga qarab turli yo‘l tanlanadi.

IF age >= 18
    status = "adult"
ELSE
    status = "minor"

Branch barcha ehtimoliy holatlarni qamrab olishi kerak.

Iteration

Bir amal takrorlanadi.

Turlari:

for;
while;
repeat-until;
iterator.

Loop termination sharti va progress aniq bo‘ladi.

Recursion

Algorithm o‘zini kichikroq masala bilan chaqiradi.

Har recursive algorithmda:

base case;
recursive step;
masalaning kichrayishi

bo‘lishi kerak.

Aks holda cheksiz recursion yuz beradi.

Time complexity

Input hajmi oshganda bajarilish vaqti qanday o‘sishi time complexity bilan baholanadi.

Big O misollari:

O(1) — constant;
O(log n) — logarithmic;
O(n) — linear;
O(n log n);
O(n²) — quadratic;
O(2ⁿ) — exponential.

Big O aniq millisekund emas, o‘sish tezligini ko‘rsatadi.

Space complexity

Algorithm qo‘shimcha qancha xotira talab qilishi.

Misol:

in-place sorting kam qo‘shimcha xotira;
merge sort O(n) yordamchi buffer talab qilishi mumkin.

Time va space o‘rtasida trade-off mavjud.

Best, average va worst case

Algorithm performance input tartibiga bog‘liq bo‘lishi mumkin.

Masalan, linear search:

best case — birinchi element;
worst case — oxirgi element yoki topilmaslik;
average — o‘rtacha pozitsiya.

Security-sensitive tizimda worst-case muhim.

Searching

Linear search

Elementlar ketma-ket tekshiriladi.

Murakkablik O(n).

Binary search

Sorted massivni yarmiga bo‘lib qidiradi.

Murakkablik O(log n).

Binary search uchun data tartiblangan bo‘lishi kerak.

Sorting

Keng tarqalgan algorithm:

bubble sort;
insertion sort;
selection sort;
merge sort;
quicksort;
heapsort;
counting sort.

Tanlov:

input hajmi;
memory;
stability;
data turi;
worst-case;
parallelism

ga bog‘liq.

Stable sorting

Teng keyga ega elementlar oldingi nisbiy tartibini saqlasa sort stable hisoblanadi.

Masalan, avval ism, keyin bo‘lim bo‘yicha stable sort kombinatsiyasi kerak bo‘lishi mumkin.

Greedy algorithm

Har bosqichda hozirgi eng yaxshi variant tanlanadi.

Ba’zi masalalarda optimal natija beradi:

minimum spanning tree;
ayrim scheduling;
Huffman coding.

Har masalada greedy tanlov global optimal natija bermaydi.

Divide and conquer

Masala kichik qismlarga bo‘linadi, qismlar yechiladi va natija birlashtiriladi.

Misollar:

merge sort;
quicksort;
binary search;
FFT.

Dynamic programming

Takroriy subproblem natijalari saqlanadi.

Yondashuvlar:

memoization — top-down;
tabulation — bottom-up.

Bu exponential recursionni polynomial yechimga aylantirishi mumkin.

Graph algorithm

Graflar uchun:

BFS;
DFS;
Dijkstra;
Bellman-Ford;
Floyd-Warshall;
topological sort;
minimum spanning tree.

Edge weight, negative cycle va graph turi tanlovga ta’sir qiladi.

Deterministic va randomized

Deterministic algorithm bir xil input uchun bir xil yo‘l va natijani beradi.

Randomized algorithm random tanlovdan foydalanadi.

Random seed test reproducibility uchun saqlanishi mumkin.

Parallel algorithm

Masala bir nechta CPU, GPU yoki node’da bajariladigan qismlarga bo‘linadi.

Muhim tushunchalar:

dependency;
synchronization;
communication cost;
load balancing;
race condition.

Barcha algorithm samarali parallel bo‘linmaydi.

Algorithm va dastur

Algorithm — yechim mantiqi.

Dastur — shu algorithmning aniq til, data structure, I/O va error handling bilan implementatsiyasi.

Bir xil algorithmning yaxshi va yomon implementatsiyasi bo‘lishi mumkin.

Testlash

Algorithm testlari:

normal input;
minimum;
maximum;
bo‘sh input;
duplicate;
sorted/reverse sorted;
invalid input;
performance;
random property.

Property-based testing umumiy qonunlarni ko‘p inputda tekshiradi.

Bog‘liq tushunchalar

Pseudocode, Flowchart, Time complexity, Space complexity, Big O, Recursion, Sorting, Searching, Dynamic programming, Graph