MergeSort algoritmining tahlili. Ushbu funktsiya first o’zgaruvchisining qiymati last o’zgaruvchisining qiymatidan kichik bo’lgan holda chaqiriladi. Middle o’zgaruvchisining qiymati hisoblanganda ro’yxat ikki qismga ajraladi. Middle o’zgaruvchisining qiymati first va last o’zgaruvchilari qiymatlarining o’rtasida joylashganligi uchun ro’yxat ikki tеng qsmga ajraladi.Har bir qism ro’yxat N/2 ta elеmеntdan iborat bo’ladi. Bunda MergeLsits algoritmning tahliliga ko’ra, birlashishi jarayonida eng yaxshi holatda N/2 ta, eng yomon holatda N/2+ N/2 -1- N-1 ta taqqoslash amali bajariladi. Bundan birlashtirish bilan saralash algoritmining murakkabligi eng yaxshi va eng yomon holatlar uchun bir xilda W(N)=B(N)=O ekanligini kеltirib chiqarish mumkin.
Do'stlaringiz bilan baham: |
