1-ma’ruza. “Ma’lumotlar tuzilmasi” faniga kirish. Asosiy tushuncha va ta’riflar. Ma’lumotlarni abstrakt toifalari

Vaqt sarfi.
Tuzilma ustida amal bajarish algoritmini bajarilish vaqtini 
hisoblash ko’zda tutiladi.Buni hisoblashdamashxur
katta “O” notatsiya 
tushunchasi ishlatiladi.
 
Xotira sarfi.
Kirish ma’lumotlarini inobatga olmagan xolda, ishlatilayotgan 
algoritm uchun xotiradan talab qilinadigan qo’shimcha joy sarfi tushuniladi.Bunda 
xam katta “O” notatsiyasi qo‘llaniladi. 
Vaqt va xotira sarfini hisoblash uchun quyidagi yondashuvlar mavjud: 
-
Katta O notatsiya
. f(x)=O(g(n)) deb belgilanadi, faqat va faqat shunday 
musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli 
bo’lsa, barcha n, n>=m holatlarda.
Masalan, ushbu funksiyani 3n+2=O(n)deb olish mumkin,chunki 3n+2<=4n, n>=2 
tengsizlik o’rinli. 
Ushbu funksiyani6*2
n
+n
2
=O(2
n
) deb olish mumkin,chunki 6*2
n
+n
2
<=7*2
n
ifoda 
o‘rinli,barcha n>=4 larda. O(1) deb hisoblash vaqti o’zgarmas bo’lgan holatni 
belgilaymiz. O(n
2
) ni kvadratik, O(n
3
) ni kubik, O(2
n
) ni eksponensial deb ataladi. 
Agar algoritmni bajarilish vaqti O(log n) bo‘lsa, O(n) ga qaraganda tezkor algoritm 
deb hisoblanadi.
-
Omega notatsiya
. f(x) = Ω(g(n)) deb belgilanadi, faqat va faqat shunday 
musbat c va m konstanta mavjud bo’lib, f(n)<=c*g(n) tengsizlik o’rinli 
bo’lsa, barcha n, n>=m holatlarda.
Masalan, 3n+2=Ω(n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1 tengsizlik 
o’rinli.6*2
n
+n
2
=Ω (2
n
) deb olish 
mumkin,chunki 6*2
n
+n
2
>=6*2
n
ifoda 
o‘rinli,barcha n>=1 larda.
-
Teta notatsiya
. f(x) = θ (g(n)) deb belgilanadi, faqat va faqat shunday 
musbat c va m konstanta mavjud bo’lib, c*g(n)<= f(n)<=c2*g(n) 
tengsizlik o’rinli bo’lsa, barcha n, n>=m holatlarda.
Masalan, 3n+2= θ (n) deb belgilash mumkin, chunki 3n+2>=3n, n>=1va 
3n+2<=4nbarcha n>=2 da tengsizlik o’rinli. 6*2
n
+n
2
=θ (2
n
) deb olish mumkin,