Algoritmlarni eng yomon va o‘rtacha holatlarda baholash. Asimptotik analiz. Algoritmlarni analiz qilish

Ma'lumotlar tuzilmalari

Shuningdek qarang: Qidiruv ma'lumotlarning tuzilishi § Asimptotik amortizatsiya qilingan eng yomon holatlar tahlili

Ma'lumotlar tarkibi	Vaqtning murakkabligi								Kosmik murakkablik
	O'rtacha: indekslash	O'rtacha: Qidiruv	O'rtacha: qo'shish	O'rtacha: O'chirish	Eng yomoni: indekslash	Eng yomoni: Izlash	Eng yomoni: kiritish	Eng yomoni: o'chirish		Eng yomoni
Asosiy qator	O (1)	O (n)	—	—	O (1)	O (n)	—	—		O (n)
Dinamik qator	O (1)	O (n)	O (n)	—	O (1)	O (n)	O (n)	—		O (n)
Yagona bog'langan ro'yxat	O (n)	O (n)	O (1)	O (1)	O (n)	O (n)	O (1)	O (1)		O (n)
Ikki marta bog'langan ro'yxat	O (n)	O (n)	O (1)	O (1)	O (n)	O (n)	O (1)	O (1)		O (n)
Hash stol	—	O (1)	O (1)	O (1)	—	O (n)	O (n)	O (n)		O (n)
Ikkilik qidiruv daraxti	—	O (log (n))	O (log (n))	O (log (n))	—	O (n)	O (n)	O (n)		O (n)
B daraxti	—	O (log (n))	O (log (n))	O (log (n))	—	O (log (n))	O (log (n))	O (log (n))		O (n)
Qizil-qora daraxt	—	O (log (n))	O (log (n))	O (log (n))	—	O (log (n))	O (log (n))	O (log (n))		O (n)
AVL daraxti	—	O (log (n))	O (log (n))	O (log (n))	—	O (log (n))	O (log (n))	O (log (n))		O (n)

• 
  Lineer qidirish ro'yxatida n elementlar. Eng yomon holatda, qidiruv har bir elementga bir marta tashrif buyurishi kerak. Bu qidirilayotgan qiymat ro'yxatdagi oxirgi element bo'lganida yoki ro'yxatda bo'lmaganida sodir bo'ladi. Biroq, o'rtacha hisobda, agar qidirilgan qiymat ro'yxatda bo'lsa va har bir ro'yxat elementi qidirilgan qiymatga teng bo'lsa, qidiruv faqat tashrif buyuradi n/ 2 ta element.