ادغام n عنصر = بدترین حالت مرتبه n
حالا اولیش میشه ۲n/k
دومی ۲n/k + n/k = 3n/k
سومی ۳n/k + n/k = 4n/k
....
...
...
آخری nk/k
و در مجموع k(k+1)/2*n/k خلاصه kهابا هم بپرن میشه مرتبه nk
البته من پایه ریاضیم ضعیفه ولی خداییش فکر نکنم غلطم باشه .
قبول دارید؟
سوالی که n تا آرایه مرتب n/k داشت بین دوتا گزینه nlogk و klogn شک داشتم و زدم nlogk فکرکنم
این سوال جز سوالات میان ترم MIT بود و می شد NK
بچه‌ها اون سوالی رو که گفته بود برای پیدا کردن میانه یک سری اعداد اون‌ها رو به دسته های پنج تایی تقسیم کرده سپس میانه هر لیست رو محاسبه و سرانجام میانه میانه‌ها رو به صورت بازگشتی محاسبه می کنیم.
اول در مورد روش حل به یه توافق برسیم بعد بریم سر زمان حلش؟
من خودم که اینجوری حسابش کردم برنامش رو هم تقریبا نوشتم .اگه ما یه لیست ۱۵ تایی در نظر بگیریم و اونو تو هر مرحله به یه سری دسته ۵ تایی تقسیم کنیم تو مرحله اول میانه این دسته‌ها به ترتیب ۳ -۸ -۱۳ میشه که این رو می تونیم به راحتی تو یه زمان ثابت به دست بیاریم.
بعد فراخوانی رو با اعداد بین این سه تا دستگیره فرواخوانی می کنیم و به همین ترتیب مثلا تو مرحله بعد ما فقط یه لیست ۵ تایی رو داریم که باید میانه اون‌ها رو حساب کنیم.
اگر کسی سوال رو حل کرده لطف کنه روش حلش رو تو وحله اول بگه.
(۲۸ بهمن ۱۳۹۰ ۱۰:۴۷ ب.ظ)mp1368 نوشته شده توسط: بچه‌ها اون سوالی رو که گفته بود برای پیدا کردن میانه یک سری اعداد اون‌ها رو به دسته های پنج تایی تقسیم کرده سپس میانه هر لیست رو محاسبه و سرانجام میانه میانه‌ها رو به صورت بازگشتی محاسبه می کنیم.
اول در مورد روش حل به یه توافق برسیم بعد بریم سر زمان حلش؟
من خودم که اینجوری حسابش کردم برنامش رو هم تقریبا نوشتم .اگه ما یه لیست ۱۵ تایی در نظر بگیریم و اونو تو هر مرحله به یه سری دسته ۵ تایی تقسیم کنیم تو مرحله اول میانه این دسته‌ها به ترتیب ۳ -۸ -۱۳ میشه که این رو می تونیم به راحتی تو یه زمان ثابت به دست بیاریم.
بعد فراخوانی رو با اعداد بین این سه تا دستگیره فرواخوانی می کنیم و به همین ترتیب مثلا تو مرحله بعد ما فقط یه لیست ۵ تایی رو داریم که باید میانه اون‌ها رو حساب کنیم.
اگر کسی سوال رو حل کرده لطف کنه روش حلش رو تو وحله اول بگه.
این توی جزوه دکتر سید جوادی فرمولش رو گفته بود:
می شه t(n/3) +T(2n/3)
(۲۸ بهمن ۱۳۹۰ ۱۰:۰۸ ب.ظ)موج نوشته شده توسط: سوالی که n تا آرایه مرتب n/k داشت بین دوتا گزینه nlogk و klogn شک داشتم و زدم nlogk فکرکنم
-==--=-==--==-=-=-=--=-=
بنظرم همین میشه.من تو یکی از سوالای سالای قبل دیده بودم.
(۲۸ بهمن ۱۳۹۰ ۰۷:۱۹ ب.ظ)temptemp2 نوشته شده توسط: جواب سوال nk بودش، چون هر دفعه کل لیست قبلی رو با بعدی مقایسه میکرد مثلا در بار اول میشه n/k و با n/k مقایسه میکنه یعنی ۲n/k عملیات o(m+n) و دفعه بعد لیست قبلی و با n/k تا عنصر بعدی ترکیب باید کنه که میشه ۳n/k و در کل میشه مجموع اعداد بالا.
که میشه o(nk)
منم با روش شما موافقم اما برا اطمینان یه نمونه n حل کردم و نتیجه از k log n
با جواب به دست اومده مطابقت داشت. سری که داشتیم ۲n/k, 3n/k ,..., k-1.n/k , n که جواب این سری نمیشه nk
(۲۸ بهمن ۱۳۹۰ ۱۱:۲۸ ب.ظ)marjane نوشته شده توسط:(28 بهمن ۱۳۹۰ ۰۷:۱۹ ب.ظ)temptemp2 نوشته شده توسط: جواب سوال nk بودش، چون هر دفعه کل لیست قبلی رو با بعدی مقایسه میکرد مثلا در بار اول میشه n/k و با n/k مقایسه میکنه یعنی ۲n/k عملیات o(m+n) و دفعه بعد لیست قبلی و با n/k تا عنصر بعدی ترکیب باید کنه که میشه ۳n/k و در کل میشه مجموع اعداد بالا.
که میشه o(nk)
منم با روش شما موافقم اما برا اطمینان یه نمونه n حل کردم و نتیجه از k log n
با جواب به دست اومده مطابقت داشت. سری که داشتیم ۲n/k, 3n/k ,..., k-1.n/k , n که جواب این سری نمیشه nk
اولا این سری باید تا kn/k بره جلو (مثلا برای یه عدد مثلا بزنید میشه جمع k-1.n/k و n/k (که آخری هستش) و بنابراین تا nk/k میره جلو)
بعدشم کلا عبارت فوق میشه
[tex]\frac{2n}{k} \frac{3n}{k} \frac{4n}{k} ... \frac{kn}{k}= \frac{n}{k}(2 3 ... k)= \frac{n}{k}(\frac{k.(k 1)}{2}-1) =\frac{n.(k 1)}{2}-\frac{n}{k} = o(nk)[/tex]
ولی من سر جلسه با چندین مدل داده مختلف و به دفعات حساب کردم klogn بدست اومد.البته من انقدر نخوندم که بتونم در مورد حل فرمولی نظر بدم
بچه‌ها من اینارو زدم شما چی؟درسته بنظرتون ؟
۹۶ - ۱
۹۷ - --
۹۸ - ۲
۹۹ - ۳
۱۰۰ - ۲
۱۰۱ - ۲
بچه ها سوال که درمورد قدرت پرایم و کراسکال بود کدوم میشد؟
(۲۹ بهمن ۱۳۹۰ ۰۱:۲۸ ب.ظ)f.b نوشته شده توسط: بچه ها سوال که درمورد قدرت پرایم و کراسکال بود کدوم میشد؟
نقل قول: من زدم کرسکال
(۲۹ بهمن ۱۳۹۰ ۰۱:۲۸ ب.ظ)f.b نوشته شده توسط: بچه ها سوال که درمورد قدرت پرایم و کراسکال بود کدوم میشد؟
من وقتی که دیدم یه دونه کامپایلر اومده کاملا گیج شدم و اومدم سوال رو ایجوری فرض کردم که این دو الگوریتم همیشه درخت با بیشترین وزن رو پیدا می کنن (مسخره بود نه )زدم هیچ کدوم . ولی با جواب afshinmu موافقم هر دو میشه یعنی ۱۸۰ درجه تفاوت با جواب من
من اون سوال رو زدم کراسکال
گفتم پریم تو بدترین حالت تو اخرین مرحله به جواب میرسه
(۲۹ بهمن ۱۳۹۰ ۰۲:۰۰ ب.ظ)aramiri نوشته شده توسط: من اون سوال رو زدم کراسکالخیر این استدلال که اشتباه هست
گفتم پریم تو بدترین حالت تو اخرین مرحله به جواب میرسه
شما اگه خروجی لحظه ای رو در نظر بگیرید برای کروسکال درختش زیر سوال میره برای پریم هم کم قدرت ترینش
به نظر من منظورش خروجی نهایی بر روی هر درخت هست