بفرمایید:
روال این طور باشه که اگه تزی دارید با یه دلیل خاصی بیان کنید! نه که از توی هوا بگید که چطور شده،
این طور بگید: (البته ببخشیدا من کسی نیستم که به کسی دیکته کنم ولی اینطور سازمان داره خیلی بهتره)
سولا فلان:
روش من:
سلام
یکی از سوالات ساختمان داده حداقل و حداکثر تعداد مقایسه ها برای ادغام دو لیست مرتب را میخواست و گزینه ها هم ترکیبی از n , 2n, 2n-1,n-1 بود
مسلما طرز فکر من اشتباه بوده چون سوال ساده به نظر میومد و من اینطوری به فکرم می رسید که در بهترین حالت بزرگترین عنصر یکی از لیست ها از کوچکترین عنصر لیست دیگر کوچکتر هستش و در نتیجه یک مقایسه کافیه صورت سوال صرفا تعداد مقایسه را خواسته بود پس هزینه رفتن به انتهای لیست شاملش نمیشه در واقع مثل عمل merg در الگوریتم mergsort الگوریتم
نهایتا این طور فکر کردم که تمام عناصر لیست اول که کوچکتر از لیست دوم هستن با عنصر اول لیست دوم در بهترین حالت مقایسه می شوند پس n مقایسه داریم که به نظرم خیلی غلط میاد
چون فردا کنکور مهندسی دارم اگه لطف کنین بگین کجا دارم اشتباه میکنم ممنون میشم حتی اگه خیلی دارم اشتباه بی سوادانه ای می کنم اشکال نداره بگین ممنون میشم
یه سوالا nlogn بود یا nlogk?
Sent from my Lenovo A3000-H using Tapatalk
صورت سوال و یکی بزاره ما واسش هرکاری میکنیم
اون ترکیب ماکس هیپ و مین هیپ چطور میشه به نظرت؟
مرتبه زمانی ادغام دو لیست مرتب به طول M و n در بهترین حالت میشه min(m,n) و در بدترین حالت میشه m+n_1 که اینجا چون طول هر دو لیست n بود پس مرتبه میشه n و ۲n_1
فکر می کنم در الگوریتم MergeSort به این صورت هست :
بدترین حالت: m + p - 1 مقایسه که چون هر دو لیست n عضو دارن میشه n + n - 1 = 2n - 1
بهترین حالت: Min(m, p) = Min(n, n) = n مقایسه که همونی که خودتون گفتید هست.
(۲۴ بهمن ۱۳۹۲ ۰۲:۲۹ ب.ظ)راضیه اکبری نوشته شده توسط: سلام
یکی از سوالات ساختمان داده حداقل و حداکثر تعداد مقایسه ها برای ادغام دو لیست مرتب را میخواست و گزینه ها هم ترکیبی از n , 2n, 2n-1,n-1 بود
مسلما طرز فکر من اشتباه بوده چون سوال ساده به نظر میومد و من اینطوری به فکرم می رسید که در بهترین حالت بزرگترین عنصر یکی از لیست ها از کوچکترین عنصر لیست دیگر کوچکتر هستش و در نتیجه یک مقایسه کافیه صورت سوال صرفا تعداد مقایسه را خواسته بود پس هزینه رفتن به انتهای لیست شاملش نمیشه در واقع مثل عمل merg در الگوریتم mergsort الگوریتم
نهایتا این طور فکر کردم که تمام عناصر لیست اول که کوچکتر از لیست دوم هستن با عنصر اول لیست دوم در بهترین حالت مقایسه می شوند پس n مقایسه داریم که به نظرم خیلی غلط میاد
چون فردا کنکور مهندسی دارم اگه لطف کنین بگین کجا دارم اشتباه میکنم ممنون میشم حتی اگه خیلی دارم اشتباه بی سوادانه ای می کنم اشکال نداره بگین ممنون میشم
در ادغام دو لیست مرتب mتایی و nتایی حداکثر n+m-1 مقایسه و حداقل (min(m,n که جواب ۲n-1 و n
قرار بر هر سوال یک تاپیک بود. از اونجا که فعلا بحث‌ها روی هواست و صورت سوالات معلوم نیست رد تایید نمیشه موضوع (بعد از اومدن کلید‌ها این موضوعات رد تایید خواهند شد)
مرتبه زمانی T(k,n) رو من زدم O(nk)
ببینید در الگوریتم merg sort در ساختمان داده انتهای دو تا لیست یک بی نهایت میذارن در نتیجه مقایسه دو لیست اینجوری میشه که میگین منتهی این جا دو لیست مرتب داریم اگه بزرگترین عنصر یکی از لیست ها از عنصر اول لیست دیگه کوچکتر باشه خب بقیه عناصر لیست اول هم کوچکتر میشن دیگه مقایسه نمیخواد
من که رفتم واسه سال دیگه ... ۴ماه شبانه روز از تموم زندگیم زدم آخرش هیچی
من این سوال رو نزدم اما اینطور فکر کردم که با هزینه nlogn از مین هیپ بر میداریم و با هزینه nlogm به مکس هیپ اضافه می کنیم که میشه nlogn + nlogm که توی گزینه ها نبود احتمالا من اشتباه می کنم جواب درست چی بوده؟
مرتبه T(n,k)=nlogn زدم..
Sent from my Lenovo A3000-H using Tapatalk
(۲۴ بهمن ۱۳۹۲ ۰۲:۳۹ ب.ظ)itsgu88 نوشته شده توسط: مرتبه زمانی T(k,n) رو من زدم O(nk)
من زدم n2k
جداقل n و حداکثر ۲n-1