Algoritm tushunchasi

O (n2) - kvadratik murakkablik. Bunday murakkablik, masalan,
element qoʻshilishi natijasida yangi saralash algoritmiga ega. Kanonik
dasturda bu ikkita ichki sikldan iborat: biri butun massivni bosib oʻtish,
ikkinchisi esa allaqachon ajratilgan qismdan keyingi element uchun joy
topish. Shunday qilib, amallar soni n*n, ya’ni n2 kabi massiv oʻlchamiga
bogʻliq boʻladi.
7 Algoritmlarning yomon, o’rta, yaxshi holatlari
Agar eng yomon holat va oʻrtacha koʻrsatkichlar bir-biridan farq
qilmasa, odatda, eng yomon holat nazarda tutiladi. Masalan, biz oʻrtacha
O(1) oʻsadigan, lekin vaqti-vaqti bilan O(n) ga aylanadigan
algoritmlarning misollarini koʻrib chiqamiz. Algoritm murakkabligining asosiy koʻrsatkichi bu muammoni hal
qilish uchun sarflanadigan vaqt va kerakli xotira hajmi.
Shuningdek, muammolar sinfi uchun murakkablikni tahlil qilishda
ma’lum bir ma’lumot miqdori - kirish kattaligini tavsiflovchi ma’lum
bir raqam aniqlanadi. Yomon, oʻrtacha yoki eng yaxshi darajadagi murakkablik tushunchalari mavjud. Odatda, eng yomon holatning murakkabligi.baholanadi.
Eng yomon holatda vaqt murakkabligi - bu berilgan kattalikdagi
masalani yechishda algoritm ishlashi davomida bajariladigan
amallarning maksimal soniga teng boʻlgan kirish kattaligining
funksiyasidir.
Eng yomon sigʻimli murakkablik - bu kirish hajmining ma’lum
hajmdagi muammolarni yechishda erishilgan maksimal xotira
yacheykalari soniga teng funksiyasi.
8 Ma’lumotlar strukturasi
Ma’lumotlar strukturasi (ing. data structure) - bu hisoblashda
turli xil bir tipli va (yoki) mantiqiy bogʻliq ma’lumotlarni saqlash va
qayta ishlashga imkon beradigan dastur birligi. Ma’lumotlarni qoʻshish,
izlash, oʻzgartirish va yoʻq qilish uchun ma’lumotlar tarkibi uning
interfeysini tashkil etadigan funksiyalar toʻplamini taqdim etadi.
“Ma’lumotlar strukturasi” atamasining bir-biriga yaqin boʻlgan bir
nechta ma’nolarini anglatuvchi variantlari mavjud:
- Ma’lumotlarning abstrakt turi;
- Ma’lumotlarning ba’zi bir abstrakt turlarini realizatsiya qilish;
- Ma’lumotlar tipining nusxasi, masalan, aniq bir roʻyxat;
- Funksional dasturlash kontekstida oʻzgarishlarda davom
etadigan noyob identifikator.
Turli xil versiyalar mavjud boʻlishiga qaramay, u norasmiy ravishda