Algoritm tushunchasi

QuickSort algoritmi tahlili. Massivni „tayanch“ elementiga
nisbatan ikki qismga boʻlish jarayoni O(log2n) vaqtni oladi. Bir xil
rekursiya darajasi bajariladigan barcha boʻlinish amallari hajmi doimiy
boʻlgan boshlangʻich massivning turli qismlarini qayta ishlagani uchun,
har bir rekursiya darajasida jami O (n) amallar ham talab qilinadi.
Shuning uchun algoritmning umumiy murakkabligi faqat boʻlinishlar
soni, ya’ni rekursiya darajasi bilan belgilanadi.
23 Graflar nazariyasi elementlari
Graflarni oʻrganish bilan shugʻullanadigan diskret matematikaning
boʻlimi “Graflar nazariyasi” deb ataladi. Graflar - bu chiziqlar bilan bogʻlangan nuqtalar toʻplami. Nuqtalar uchlar (tugunlar) chiziqlar esa qirralar (yoylar) deb nomlanadi. Graf - bu abstrakt obyekt boʻlib, uchlar toʻplami (tugunlar) vaqirralarning toʻplami - uchlar juftliklari orasidagi bogʻlanishlardan tashkil topadi (ulanishlar). G graf - G: = (V, E) tartiblangan juftlik, bu yerda V – uchlarning (yoki tugunlarning) boʻsh boʻlmagan toʻplami, E esa qirralar deb nomlangan uchlarning juftlari toʻplamidir. Grafning uchlari va qirralari (ular graf elementlari deb ataladi), grafdagi uchlar soni | V | - graf tartibi, qirralarning soni | E | - graf hajmi deb ataladi.

24 Graflar nazariyasi haqida umumiy ma’lumotlar
Graf - bu abstrakt obyekt boʻlib, uchlar toʻplami (tugunlar) va
qirralarning toʻplami - uchlar juftliklari orasidagi bogʻlanishlardan
tashkil topadi (ulanishlar). Grafdagi marshrut - bu har bir uch (oxirgisidan tashqari) ketmaketlikdagi keyingi uchga qirra bilan bogʻlangan uchlarning cheklangan ketma-ketligi.
Yoʻl - bu qirralarning takrorlanmagan yoʻlidir. Oddiy zanjir - bu
uchlarni takrorlamaydigan marshrut (bu oddiy zanjirda takrorlanadigan
qirralarning yoʻqligini anglatadi)
Orgrafdagi yoʻnaltirilgan marshrut (yoki yoʻl) - bu har bir
element oldingi va keyingi qismga tushadigan uchlar va yoylarning
cheklangan ketma-ketligi. Yoʻlning (yoki siklning) uzunligi uni tashkil etuvchi qirralarning soni deyiladi
Agar uning qirralari takrorlanmasa, yoʻl (yoki sikl) oddiy deb
nomlanadi; agar u sodda boʻlsa va undagi tepaliklar takrorlanmasa u