(۱۷ بهمن ۱۳۹۲ ۱۲:۰۵ ق.ظ)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]

(۱۷ بهمن ۱۳۹۲ ۱۲:۳۰ ق.ظ)e.shrm نوشته شده توسط:  ممنون. برای دومی اینو ببینید :
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

برای دومی من پیش فرض i را کوچک و ثابت فرض کردم. تو این سوال i را وابسته به n گرفته و خودش گفته i بیشتر از n/2 . پس به جای n میشه i هم گذاشت. عبارت دقیقشو باید حساب کرد که بازم بعید میدونم ilogi بشه .

(۱۷ بهمن ۱۳۹۲ ۱۲:۱۰ ق.ظ)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 عنصر درآخر نیاز به مرتب سازی نداره، بخاطر اینه که سوال نمیخواد دقیقا بدونه مثلا دومین بزرگترین عنصر دقیقا چه عنصری هست؟

اینو ببینید لطفا برای موزد دوم :

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

------------------------------
آقای Riemann ، در مورد اون دو تای دیگه چی؟

به نظر منم 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 log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟

این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

(۲۰ بهمن ۱۳۹۲ ۱۲:۴۸ ق.ظ)masoud67 نوشته شده توسط:  

(20 بهمن ۱۳۹۲ ۱۲:۱۷ ق.ظ)Good! نوشته شده توسط:  این مشابه همون روش جوانترین پدر هست؟البته روش جوانترین پدر n log n هست.
ممنون ولی کامل متوجه نشدم.مثلا اینکه آخرین گره پدر رو چطور پیدا میکنه؟و اینکه بعدا بخواد پدر همین آخرین پدر رو با بچه هاش مقایسه کنه اگه اون آخرین پدر با پدرش جاش عوض بشه و اونوقت باعث بشه که همینطوری تا پایین جاشون عوض شه میشه همونn log n که
when all elements are distinct, the best-case running time of heapsort
is (n lg n).
این جمله از CLRS هست.میشه شما بگید کدوم صفحه اون روش رو نوشته؟

این دقیقا همونه که در ظاهر n/2 بار تابع maxheap را که مرتبه logn داره را فراخوانی میکنه. و به ظاهر میشه nlogn
اما اگه دقیقتر حساب بشه میشه مرتبه n چون در هر ارتفاعی maxheap یه مرتبه به خصوصی داره و همیشه logn نیست
من فایل اثباتشو ضمیمه کردم و اینجا هم هست

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.


و برای سوال دوم موضوع اصلی تاپیک هم ، این سوال و جواب را از تمرینات CLRS پیدا کردم

مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.

واقعا لطف کردید.ممنون.گرچه اون اولی دو خط آخر اثباتشو متوجه نشدم

(۲۰ بهمن ۱۳۹۲ ۰۱:۱۱ ق.ظ)Good! نوشته شده توسط:  واقعا لطف کردید.ممنون.گرچه اون اولی دو خط آخر اثباتشو متوجه نشدم

چون h مقدار خطی و [tex]2^{h}[/tex] مقدار نمایی هست و مقدار h خیلی از کمتر مقدار نمایی میشه ، h را یک در نظر گرفته و بقیه اش دیگه واضحه

(۲۰ بهمن ۱۳۹۲ ۰۹:۰۴ ق.ظ)masoud67 نوشته شده توسط:  

(20 بهمن ۱۳۹۲ ۰۱:۱۱ ق.ظ)Good! نوشته شده توسط:  واقعا لطف کردید.ممنون.گرچه اون اولی دو خط آخر اثباتشو متوجه نشدم

چون h مقدار خطی و [tex]2^{h}[/tex] مقدار نمایی هست و مقدار h خیلی از کمتر مقدار نمایی میشه ، h را یک در نظر گرفته و بقیه اش دیگه واضحه

تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشم
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟

(۲۱ بهمن ۱۳۹۲ ۱۲:۵۸ ق.ظ)Good! نوشته شده توسط:  تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشم
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟

خودتو درگیرش نکن. بدیهی بگیر برو
سوالی که من گذاشتم (که نباید میذاشتم) واسه زمانی بود که i عدد ثابت هست ولی صورت سوالی که دوستمون گذاشته بودند (نه در پست اول ، بلکه چند تا پست پایین تر) i وابسته n بوده به همین خاطر به جای n میتونیم i بذاریم که دقیقتر میشه

(۲۱ بهمن ۱۳۹۲ ۰۸:۰۶ ق.ظ)masoud67 نوشته شده توسط:  

(21 بهمن ۱۳۹۲ ۱۲:۵۸ ق.ظ)Good! نوشته شده توسط:  تشکر گرچه بازم متوجه نشدم.طریقه به دست آوردن یک دوم به توان h رو متوجه میشم اما اون خط آخر که تو مخرج ۱ منهای ۱/۲ به توان ۲ هست رو متوجه نمیشم
در ضمن جوابی که شما از clrs پیدا کردید نوشته n+ilogn در صورتیکه یکی دیگه از دوستان یه جواب از کتاب دیگه ای گذاشتن که n+ilogi بود.حالا کدوم درسته؟؟:؟

خودتو درگیرش نکن. بدیهی بگیر برو
سوالی که من گذاشتم (که نباید میذاشتم) واسه زمانی بود که i عدد ثابت هست ولی صورت سوالی که دوستمون گذاشته بودند (نه در پست اول ، بلکه چند تا پست پایین تر) i وابسته n بوده به همین خاطر به جای n میتونیم i بذاریم که دقیقتر میشه

اوکی پس ینی جواب سوال اولین پست میشه n+ilogn ولی اونی که i رو وابسته به n گرفته میشه n+ilogi?
اوکی ممنون