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
Do'stlaringiz bilan baham: |
