(۱۰ آذر ۱۳۹۱ ۰۴:۲۲ ب.ظ)sufia_lido نوشته شده توسط:  یکی بگه پیچیدگی بدست آوردن میانه بالاخره چقدره؟ آخه سوال مهندسی کامپیوتر۸۳ که (مربی میخواد فاصله اش از همه دانشجو ها کمینه شود) و سوال علوم کامپیوتر ۸۷ (میانه ۲ آرایه)... هر دو پیچیدگی بدست آوردن میانه هستن. اما اولی از مرتبهN و دومی logN
البته دومی سوال طراحی الگوریتمه

با سلام:
دوست عزیز تا اونجایی که من میدونم پیچیدگی زمانی انتخاب kامین عنصر کوچک از مرتبه [tex]o(n)[/tex] هست خب حالا چرا اینا نوشتم میانه مگه حالت خاصی با [tex]k=n/2[/tex] نیست؟؟؟؟پس مرتبه به دست اوردن میانه [tex]o(n)[/tex] هست/...
حالا نمیدونم چرا جوابا تطابق ندارن؟؟؟
موفق و پیروز باشید یا حق/...

منم یه جا خوندم که محاسبه ماکسیمم و مینیمم و میانه o(n) هست اما روش deh-ab به نظرم غلطه چون در اصل پیدا کردن k کوچکترین میشه o(nlogk) که اگه k<<n باشه می تونیم بنویسیم o(n) نه اینکه k باشه n/2 در این صورت میشه o(nlog(n/2)) یعنی o(nlogn)
این زمانی هست که مثلا ۱۰۰۰ تا داده داریم و می خواهیم ۵ امین کوچکترین یا همین مقدارو پیدا کنیم نه اینکه ۵۰۰ امین کوچکترین!!!!

پیدا کردن میانه خودش الگوریتم خاصی داره که بشه o(n) به این کشکی نیست به نظرم

(۳۰ دى ۱۳۹۱ ۱۲:۵۸ ق.ظ)mahdiii نوشته شده توسط:  منم یه جا خوندم که محاسبه ماکسیمم و مینیمم و میانه o(n) هست اما روش deh-ab به نظرم غلطه چون در اصل پیدا کردن k کوچکترین میشه o(nlogk) که اگه k<<n باشه می تونیم بنویسیم o(n) نه اینکه k باشه n/2 در این صورت میشه o(nlog(n/2)) یعنی o(nlogn)
این زمانی هست که مثلا ۱۰۰۰ تا داده داریم و می خواهیم ۵ امین کوچکترین یا همین مقدارو پیدا کنیم نه اینکه ۵۰۰ امین کوچکترین!!!!

پیدا کردن میانه خودش الگوریتم خاصی داره که بشه o(n) به این کشکی نیست به نظرم

سلام:
دوست عزیز این روش من نیست روش حل جناب اقای یوسفی مولف کتاب ساختمان داده و طراحی الگوریتم پوران هست/...
موفق و پیروز باشید یا حق/...

برای قسمت دوم هم که مساله فرق داره به نظرم یعنی دو لیست مرتب داده شده با n عنصر هر کدام و می خوایم میانه را تو اجتماع اینها به دست بیاریم که میشه همون مساله یافتن nامین کوچکترین که با تقسیم مشابه جستجوی باینری میشه log ایو تو یکی از همین صفحاتم بچه ها گذاشته بودن. بازم اگه سوال بود برای قسمت دوم بگید توضیح بدم چرا شد log ای ولی برای قسمت اول یکی بیاد بگه چرا پیدا کردن میانه میشه o(n)

---

(۳۰ دى ۱۳۹۱ ۰۱:۰۴ ق.ظ)deh-ab نوشته شده توسط:  

(30 دى ۱۳۹۱ ۱۲:۵۸ ق.ظ)mahdiii نوشته شده توسط:  منم یه جا خوندم که محاسبه ماکسیمم و مینیمم و میانه o(n) هست اما روش deh-ab به نظرم غلطه چون در اصل پیدا کردن k کوچکترین میشه o(nlogk) که اگه k<<n باشه می تونیم بنویسیم o(n) نه اینکه k باشه n/2 در این صورت میشه o(nlog(n/2)) یعنی o(nlogn)
این زمانی هست که مثلا ۱۰۰۰ تا داده داریم و می خواهیم ۵ امین کوچکترین یا همین مقدارو پیدا کنیم نه اینکه ۵۰۰ امین کوچکترین!!!!

پیدا کردن میانه خودش الگوریتم خاصی داره که بشه o(n) به این کشکی نیست به نظرم

سلام:
دوست عزیز این روش من نیست روش حل جناب اقای یوسفی مولف کتاب ساختمان داده و طراحی الگوریتم پوران هست/...
موفق و پیروز باشید یا حق/...

ای کاش بگین تو کتاب از چه روشی k کوچکترین رو پیدا کرده؟

(۳۰ دى ۱۳۹۱ ۱۲:۵۸ ق.ظ)mahdiii نوشته شده توسط:  منم یه جا خوندم که محاسبه ماکسیمم و مینیمم و میانه o(n) هست اما روش deh-ab به نظرم غلطه چون در اصل پیدا کردن k کوچکترین میشه o(nlogk) که اگه k<<n باشه می تونیم بنویسیم o(n) نه اینکه k باشه n/2 در این صورت میشه o(nlog(n/2)) یعنی o(nlogn)
این زمانی هست که مثلا ۱۰۰۰ تا داده داریم و می خواهیم ۵ امین کوچکترین یا همین مقدارو پیدا کنیم نه اینکه ۵۰۰ امین کوچکترین!!!!

پیدا کردن میانه خودش الگوریتم خاصی داره که بشه o(n) به این کشکی نیست به نظرم

deh-ab درست جواب داده. شما داری اشتباه میکنی