Ma’lumotlar tuzilmasi Data structures 4-ma’ruza: Saralash usullari

T(n)=2T(n/2)+O(n)

Бу ерда O(n) – иккита массивни аралаштириш учун сарфланган вақт.

Бу муносабатни ёйиб чиқсак қуйидаги ҳолатга эга бўламиз:

T(n)=2T(n/2)+O(n)=4T(n/4)+2O(n/2)+O(n)=4T(n/4)+2O(n)= … = 2kT(1)+kO(n)

Алгоритмнинг самарадорлиги

Олинган натижадан кўриниб турибдики, фақат k ни баҳоласак мақсадга эришилади. Бизга маълумки, 2k=n. Бундан k=log2n келиб чиқади.

У ҳолда юқоридаги тенглама қуйидаги кўринишни олади:

T(n)=n*T(1)+log2n*O(n).

Бу ерда T(1) константда, бундан эса

T(n)=O(n)+log2nO(n)=O(n*log2n)

Олинган натижадан хулоса қилиб айтиш мумкинки, олдинги ўрганилган тўғридан-тўғри саралаш ва Шейкер усулидаги алгоритмларга нисбатан аралаштириб саралаш алгоритми тез ишлайди. Чунки, олдинги алгоритмлар T(n)=O(n2) – вақтда бажарилади.

Adabiyotlar

• [RU] Алфред В. Ахо., Джон Э. Хопкрофт, Джефри Д. Ульман. Структура данных и алгоритмы. //Учеб.пос., М.: Изд.дом: "Вильямс", 2000, — 384 с.
• [EN] Adam Drozdek. Data structures and algorithms in C++. Fourth edition.Cengage Learning, 2013.
• [UZ] Narzullaev U.X., Qarshiev A.B., Boynazarov I.M. Ma’lumotlar tuzilmasi va algoritmlar. //O’quv qo’llanma. Toshkent: Tafakkur nashriyoti, 2013 y. – 192 b.
• [RU] Лойко В.И. Структуры и алгоритмы обработки данных. Учебное пособие для вузов. - Краснодар: КубГАУ. 2000. - 261 с., ил.

Mustaqil ishlash uchun topshiriqlar:

• Tashqi saralash algoritmlarini o’rganish va misollar yechish
• Izoh: dars mashg’ulotida berilgan bilimlarga qo’shimcha ma’lumotlarni to’plash-konspekt qilish