صفحه‌ها: ۱ ۲
سلام.
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
(۱۷ بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:ممنون. برای دومی اینو ببینید :(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
برای مورد سوم من میگم میشه i*n. وگرنه طبق گفته شما میشه n^2 نه ۲n.
(۱۷ بهمن ۱۳۹۲ ۰۷:۴۹ ق.ظ)fulgent نوشته شده توسط: برای مورد سوم من میگم میشه i*n. وگرنه طبق گفته شما میشه n^2 نه ۲n.
چرا؟! i امین رو که پیدا کنیم تو n ، کافیه حول اون پارتیشن کنیم ، اونوقت هرچی از i بیشتر میره بالا دیگه ؟
(۱۷ بهمن ۱۳۹۲ ۰۸:۰۵ ق.ظ)e.shrm نوشته شده توسط:(17 بهمن ۱۳۹۲ ۰۷:۴۹ ق.ظ)fulgent نوشته شده توسط: برای مورد سوم من میگم میشه i*n. وگرنه طبق گفته شما میشه n^2 نه ۲n.
چرا؟! i امین رو که پیدا کنیم تو n ، کافیه حول اون پارتیشن کنیم ، اونوقت هرچی از i بیشتر میره بالا دیگه ؟
واسه دومی به نظر من میشه [tex]n (\lg n \lg (n-1) \dots \lg(n - i 1) )[/tex]
ولی نمیدونم اینو ساده کنیم به اون چیزی که شما میگی میرسیم یا نه!
ولی یه طوری میشه چک کنی که شما اگه n تا عدد اول رو بکشی بیرون بیاد یه چیزی حدود nlgn بشه که اونم میشه! و اون چیزی که من نوشتم هم فکر کنم بشه
[tex]n \lg(n!) = n n\lg n \in \Omega(n\lg n)[/tex]
اینو ببینید لطفا برای موزد دوم :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
------------------------------
آقای Riemann ، در مورد اون دو تای دیگه چی؟
(۱۷ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)e.shrm نوشته شده توسط: ممنون. برای دومی اینو ببینید :برای دومی من پیش فرض i را کوچک و ثابت فرض کردم. تو این سوال i را وابسته به n گرفته و خودش گفته i بیشتر از n/2 . پس به جای n میشه i هم گذاشت. عبارت دقیقشو باید حساب کرد که بازم بعید میدونم ilogi بشه .
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)masoud67 نوشته شده توسط:اینکه میگین i عنصر درآخر نیاز به مرتب سازی نداره، بخاطر اینه که سوال نمیخواد دقیقا بدونه مثلا دومین بزرگترین عنصر دقیقا چه عنصری هست؟(17 بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)e.shrm نوشته شده توسط: سلام.اولی درست
درست است یا نه؟ ی
۱- استفاده از مرتب سازی : nlogn
۲- استفاده از یک هیپ و i بار extract max : م n + i log i
۳- یافتن i امین عنصر (مرتبه n) و تقسیم بر اساس آن و مرتب سازی i عدد بزرگ : n + i log i
دومی n+ilogn
سومی به نظرم درسته ولی یه کار بهتر اینکه فقط i امین عنصر را پیدا کنیم و بدیمش به پارتیشن و پاریتیشن هم عناصر بزرگتر از i را ببره طرف راستش. حالا ما طرف راست عناصر بزرگتر از i را داریم و دیگه نیازی به مرتب سازی هم نداریم و مرتبه میشه n برای پیدا کردن عنصر i و n هم برای پارتیشن و در کل ۲n
به نظر منم n+ilogi درسته وهمیشه جواب می ده!
این سوال مثل سوال ۱۱۲ هست من امروز صبح در این قسمت آخر page نوشتمش و توضیحم بر اساس توضیحاتیه که دکتر یوسفی گفتن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
فقط تو اونجا k تا کوچکه رو می خواسته اینجا i تا بزرگتر رو!
(۱۷ بهمن ۱۳۹۲ ۱۰:۱۳ ب.ظ)mahsalove نوشته شده توسط: به نظر منم n+ilogi درسته وهمیشه جواب می ده!
این سوال مثل سوال ۱۱۲ هست من امروز صبح در این قسمت آخر page نوشتمش و توضیحم بر اساس توضیحاتیه که دکتر یوسفی گفتن:
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
فقط تو اونجا k تا کوچکه رو می خواسته اینجا i تا بزرگتر رو!
یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟
(۱۹ بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)Good! نوشته شده توسط: یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟اگر از روش درج متوالی استفاده بشه از مرتبه nlgn میشه اما روش دیگه‌ای وجود داره که از آخرین گره‌ی پدر (یعنی پایینترین و سمت راست‌ترین پدر) شروه به هیپ کردن درخت میکنه که این روش از مرتبه n هستش. تو CLRS فصل heapsort کاملا توضیح داده
(۱۹ بهمن ۱۳۹۲ ۱۱:۳۸ ب.ظ)mfXpert نوشته شده توسط:(19 بهمن ۱۳۹۲ ۱۱:۳۳ ب.ظ)Good! نوشته شده توسط: یکی لطف میکنه به من توضیح بده چطوری هیپ رو تو تتای n میسازن؟؟اگر از روش درج متوالی استفاده بشه از مرتبه nlgn میشه اما روش دیگه‌ای وجود داره که از آخرین گره‌ی پدر (یعنی پایینترین و سمت راست‌ترین پدر) شروه به هیپ کردن درخت میکنه که این روش از مرتبه n هستش. تو CLRS فصل heapsort کاملا توضیح داده
این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
(۲۰ بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)Good! نوشته شده توسط: این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
(۲۰ بهمن ۱۳۹۲ ۱۲:۴۸ ق.ظ)masoud67 نوشته شده توسط:(20 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)Good! نوشته شده توسط: این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
واقعا لطف کردید.ممنون.
گرچه اون اولی دو خط آخر اثباتشو متوجه نشدم