O‘zbekiston respublikasi axborot texnologiyalari va kommunikatsiyalarini rivojlantirish vazirligi muhammad al-xorazmiy nomidagi toshkent axborot texnologiyalari universiteti algoritmlarni loyihalash fanidan Abdullayev Muxammadalining yozgan Mustaqil

m hissasini qo'shadi (ammo bu ibora ishlatilgan xotira hajmini hisoblash uchun ishlatilmaydi). Barcha qatorlarning hissalarini qo'shsak, olamizInsertion-Sort protsedurasining umumiy bajarilish vaqtini hisoblash uchun har bir satrda uning narxini (operatsiyalar soni) va ushbu satrning necha marta bajarilishini hisobga olamiz. 2 dan n gacha bo'lgan har bir j uchun (bu erda n = uzunlik [A] - massiv o'lchami), 5 qatori necha marta bajarilishini hisoblash kerak, biz bu raqamni tj bilan belgilaymiz. Davr ichidagi chiziqlar cheklovga qaraganda bir marta kamroq bajariladi, chunki oxirgi tekshirish pastadirdan chiqadi. Bir necha marta takrorlangan m satr bajarilgan operatsiyalar umumiy soniga c

Jarayonning ishlash vaqti nafaqat n ga bog'liq, balki kirishning kirish qismida n o'lchamining qaysi qatori bilan ta'minlanganligiga ham bog'liq. Insertion-Sort protsedurasi uchun massiv allaqachon tartiblangan bo'lsa, eng maqbul holat. Keyin 5-chiziqdagi tsikl birinchi tekshiruvdan so'ng tugaydi (chunki A [i] ≤ tugmachasi i = j - 1), shunda hamma tj 1 ga teng, jami vaqt esa

 

n + b shakli mavjud. Ushbu konstantalar tanlangan qiymatlar bilan belgilanadi c1, ..., c8.Shunday qilib, eng qulay holatda n o'lchovli qatorni saralash uchun zarur bo'lgan vaqt (n), n ning chiziqli funktsiyasi. a va b ba'zi turg'unliklar uchun T (n) = a

Agar qator teskari (pasayish) tartibda joylashgan bo'lsa, ish vaqti

protsedura maksimal bo'ladi: A [j] har bir elementni A [1], ..., A [j - 1] barcha elementlar bilan taqqoslash kerak. Bundan tashqari, tj = j. Chunki

biz eng yomon holatda protsedura vaqti ekanligini tushunamiz

n + s shakliga ega. A, b va c konstantalari bu erda ham c1, ..., c8 qiymatlari bilan aniqlanadi.n2 + bBunday holda, T (n) kvadratik funktsiya, ya'ni. T (n) = a

Odatda algoritmning vaqt murakkabligi n o'lchamidagi ma'lumotlardan T (n) tartibiga to'g'ri keladi, deyiladi. Amaliyotda T (n) ning aniq qiymatini aniqlash juda qiyin. Shuning uchun ular O-simvolizmidan foydalanib, asimptotik munosabatlarga murojaat qilishadi.

• 
  Insertion sort da n ta har xil va tasodifiy tartibda joylashtirilgan elementlarning ro'yxatiga qo'llaniladi . O'rtacha, A ro'yxatidagi elementlarning yarmi A 1 ... A j elementlar A j +1 elementlaridan kamroq , yarmi esa kattaroqdir. Shuning uchun, algoritm  o'rtacha ( j + 1) th elementni allaqachon saralangan ichki ro'yxatning yarmi bilan taqqoslaydi , shuning uchun t j = j / 2. Olingan o'rtacha ish vaqtini ishlab chiqish, eng yomon ish vaqti kabi, kirish hajmining kvadratik funktsiyasini ham beradi.
  
• 
  Quicksortda n ta elementlarning ro'yxatiga qo'llaniladi , ular yana barchasi har xil va tasodifiy ravishda qabul qilingan. Ushbu mashhur saralash algoritmi O ( n  log ( n )) o'rtacha ish ko'rsatkichiga ega va bu uni amalda juda tez algoritmga aylantirishga yordam beradi. Ammo eng yomon holatlarda, uning ishlash ko'rsatkichi O ( n 2 ) ga pasayadi . Bundan tashqari, "eng qisqa birinchi" siyosati bilan amalga oshirilganda, eng yomon holatda kosmik murakkablik O (log ( n )) bilan chegaralanadi .