سلام
ببخشید برای پیداکردن x عنصر از کوچکترین عناصر یک آرایه! باید چیکار کنیم؟؟؟
مدرسان گفته میشه (O(n ....
آخه چطوری ؟؟
مگر ما نباید اول یه پیمایش کنیم تا min بدست بیاد....=> بعدش دوباره این رو حذف کنیم سپس مینیمم بدست بیاریم...این ک خیلی میشه!
باتشکر
(۰۸ بهمن ۱۳۹۳ ۱۰:۵۱ ق.ظ)mostafa2012 نوشته شده توسط: سلام
ببخشید برای پیداکردن x عنصر از کوچکترین عناصر یک آرایه! باید چیکار کنیم؟؟؟
مدرسان گفته میشه (O(n ....
آخه چطوری ؟؟
مگر ما نباید اول یه پیمایش کنیم تا min بدست بیاد....=> بعدش دوباره این رو حذف کنیم سپس مینیمم بدست بیاریم...این ک خیلی میشه!
باتشکر
اگه منظورتون xامین کوچکترین هست با selection میشه تویه n پیداش کرد
ولی اگه متناوب x تا کوچکترین رو میخوای باید تا حدی از مرتب سازی استفاده کنی تا xتا در بیاد ک میشه nlogx یا میشه n+xlogx ک اگه x کوچیک باشه میشه n
با استفاده از الگوریتم انتحاب x امین عنصر ازایه را در مرتبه [tex]O(n)[/tex] پیدا میکنیم و این عنصر را محور قرار میدیم و ارایه را پارتیشن بندی میکنیم. اعناصری که سمت چپ ارایه قرار دارند از ایکس کوچکتر هستند که با مرتبه [tex]O(x)[/tex] این اعداد رو جمع میکنیم که در کل
مرتبه الگوریتم [tex]O(n)[/tex] میشه (x<n)
(۲۷ دى ۱۳۴۸ ۰۳:۳۷ ب.ظ)maryam.roshan نوشته شده توسط: [X نه!
اعناصری که سمت چپ ارایه قرار دارند از ایکس کوچکتر هستند که با مرتبه x این اعداد رو جمع میکنیم که در کل
چرا جمع اصلا?
مرتب سازی ش Xlogx میشه ! البته انگار مرتب لازم نیست باشه اگه اینطوریه این هزینه رو نداری
همون فرمولی ک نوشتم n+xlogx با مرتب سازی x عنصر
ببخشید من فک کردم که گفتید جمعشون!
عنصر x ام را با الگوریتم انتحاب پیدا میکنیم و حول اون پارتیشن بدی میکنیم. تمام
اعداد سمت چپ میشه x عنصر کوچک.که مرتبه ش [tex]O(n)[/tex] میشه
جال اگه گفته بود بصورت مرتب که میشد [tex]O(n xlogx)[/tex]