سلام
سوال اینه:
فرض کنید k عدد آرایه مرتب به طول n داریم. هدف ادغام این آرایه ها و ساختن یک آرایه مرتب است. بهترین الگوریتم برای این کار چه هزینه ای دارد؟
۱)[tex]\Theta (nk)[/tex]
۲[tex]\Theta (k log(n))[/tex]
۳)[tex]\Theta (n log(k)[/tex]
۴[tex]\Theta (n k log(k))[/tex]
گزینه صحیح گزینه ۴
پاسخنامه هم ضمیمه شده
حالا سوال من اینه: مگه نمیشه با مین هیپ k تا لیست n تایی رو در زمان O(n log k) ادغام کرد؟ زمانش هم بهتر از گزینه ۴ هست!
سوال غلطه به نظرتون؟ یا من اشتباه میکنم؟
یه چیزی میگم نمیدونم درست باشه یا نه.
اگه منظورتون از مین هیپ و ادغام k آرایه باشه (فکر کنم بهش میگفتیم درخت تورنمنت) اینطور که یادمه هر تجدید ساختار میشد logk و اینجا nk تا کلید داریم و در مجموع میشه nklogk
اما اگه منظورتون ادغام هیپ ها هست که در زمان logn انجام میشه ، ظاهرا ادغام هیپ ها منجر میشه به درخت هیپ دوجمله ای یا هیپ فیبوناچی (دقیق یادم نیست) و این هیپ دو جمله ای مشتکل از چند تا درخت هیپه و یه درخت دودویی نیست که بگیم چون هیپ ها را ادغام کردیم پس همه چی مرتب شده. چون یه گره میتونه بیش از دو فرزند داشته باشه وبرای مرتب کردنش باید nk تا کلید را در زمان logk حذف و در آرایه جدید قرار داد
بازم نمیدونم چیزی که میگم درسته یا نه ولی احساس میکنم دلیلش این باشه
(29 دى 1392 06:46 ب.ظ)masoud67 نوشته شده توسط: [ -> ]یه چیزی میگم نمیدونم درست باشه یا نه.
اگه منظورتون از مین هیپ و ادغام k آرایه باشه (فکر کنم بهش میگفتیم درخت تورنمنت) اینطور که یادمه هر تجدید ساختار میشد logk و اینجا nk تا کلید داریم و در مجموع میشه nklogk
اما اگه منظورتون ادغام هیپ ها هست که در زمان logn انجام میشه ، ظاهرا ادغام هیپ ها منجر میشه به درخت هیپ دوجمله ای یا هیپ فیبوناچی (دقیق یادم نیست) و این هیپ دو جمله ای مشتکل از چند تا درخت هیپه و یه درخت دودویی نیست که بگیم چون هیپ ها را ادغام کردیم پس همه چی مرتب شده. چون یه گره میتونه بیش از دو فرزند داشته باشه وبرای مرتب کردنش باید nk تا کلید را در زمان logk حذف و در آرایه جدید قرار داد
بازم نمیدونم چیزی که میگم درسته یا نه ولی احساس میکنم دلیلش این باشه
آره منظورم همون اولی بود! ممنون بابت توضیحاتتون فهمیدم اشتباه کجاست! و به نظرم درست میگین. چیزی که خونده بودم n رو تعداد کل خونه ها گرفته در نتیجه تو این سوال تعداد کل خونه ها میشه nk و در نتیجه nk logk
بازم ممنون
موفق باشید
(29 دى 1392 09:15 ب.ظ)30noohe نوشته شده توسط: [ -> ]چیزی که خونده بودم n رو تعداد کل خونه ها گرفته در نتیجه تو این سوال تعداد کل خونه ها میشه nk و در نتیجه nk logk
منم دقیقا همین اشتباهو کردم و تو آزمون غلط زدم. فکر کردم کلا n عنصر داریم. ولی بعد فهمیدم nk عنصر داریم