سلام
چرا سنجش گزینه ۴رو گزینه صحیح اعلام کرده!!
خب تو بدترین حالت برای nعنصر هر بیت رو با بیت کناریش جمع میکنی بعد حاصل رو دوباره با بیت کناری همینجور تا اخر ک میشه nتا!
ی حالتم اینه n تا بیت رو بصورت جمع دوتاn/2بیتی درنظر بگیریم یعنی بصورت تقسیم و حل!ک بدترین حالت میشه nlogn.چون درخت بازگشتی ک میشه به ارتفاع logn.
متوجه منظورتون نمیشم
یعنی چی بیت کناریش؟
بیت کناری مگه وجود داره؟
میگه ۱ بیتی
آها تازه متوجه سوال شدم
بله حق با شماست
(۳۰ دى ۱۳۹۳ ۱۱:۵۲ ق.ظ)tm.viper نوشته شده توسط: متوجه منظورتون نمیشمبلاخره چی شد حداکثر میشهnیاnlogn????
یعنی چی بیت کناریش؟
بیت کناری مگه وجود داره؟
میگه ۱ بیتی
آها تازه متوجه سوال شدم
بله حق با شماست
تو صورت سوال یه روشی رو خودش در نظر گرفته که اگه با اون روش این اعداد رو جمع کنیم مرتبه زمانیش میشه ماکسیمم a و b و گفته که هزینه این کار بسته به ترکیب داده ورودی ممکن است متفاوت باشد(منظورش اینه که روش جمع همین یک روشه فقط مقادیر ورودی متفاوته)، یعنی بسته به مقادیر ورودی مرتبه زمانی فرق می کنه، اگه پرسیده بود سریع ترین روش و کند ترین روش جمع کردن (یا یه همچین چیزی) اون موقع رو راه حل ها فکر میکردیم ولی تو این سوال مرتبه زمانی جمع دو عدد n بیت رو خودش داده فقط باید ببینیم با چه مقادیری عمل اصلی که جمع کردنه حداقل میشه و با چه مقادیری حداکثر میشه
حالا اگه ما اینطوری فکر کنیم که بدترین حالت یا بهترین حالت فرقی نمیکنه و ما برای جمع کردن n عدد یک بیتی باید n-1بار عددهای یک بیتی رو با هم جمع کنیم، مرتبه زمانی هر جمع میشه [tex]O(\max(1,1))[/tex] یا همون [tex]O(1)[/tex] . که مرتبه زمانی انجام n-1 بار این عمل میشه [tex]O(n)[/tex]
البته این تست در کمال نامردی طراحی شده چون چند جور برداشت میشه ازش کرد و برداشتی که من خودم موقع حل کردن ازش کرده بودم این بود که تو بهترین حالت n تا صفر رو با هم جمع می کنیم و هربار باید نتیجه رو با صفر بعدی جمع کنیم که هِی صفر میشه و همون جمع یک بیتی ها هستش و مرتبش میشه [tex]O(n)[/tex] ، و تو بدترین حالت n تا یک رو با هم جمع می کنیم و هربار یک رو با نتیجه قبلی جمع می کنیم که مرتبش میشد [tex]O(nlogn)[/tex] (چون تعداد بیت های نتایج هِی زیادتر میشد)
من مجاب نشدم چرا حداقل هم از مرتبه n میشه!!
صورت سوال فقط گفته هزینه دو عدد aبیتی,bبیتی میشه ماکسشون!!..نگفته چجوری جمع کنی!!
شما nتا ۱داشته باشه بصورت ۲تا ۲تا جدا کن جمع کن!!یعنی هربار دو عدد ۱بیتی که شکل ی درخت پر دودویی میشه!!
حالا چون همه nتا عدد ۱هستن ممکنه حاصل جمع بیت اضافه تولید کنه ..اینجور نیس که همیشه همون ۱بیت بمونه!!!!!!!!!...ک بگیم nتا عمل با هزینه ۱میشه !!
اینجور ک من میگم هربار ی بیت داره اضافه میشه چون عمق درختم log nهست میشه جمع از ۱تا logn!!ک میشه از مرتبه [tex]O(\log\: n)[/tex]
(۰۳ بهمن ۱۳۹۳ ۰۲:۴۷ ب.ظ)shamim_70 نوشته شده توسط: من مجاب نشدم چرا حداقل هم از مرتبه n میشه!!شما حداقل رو که خودتون گفتین میشه مرتبه n ، اونو حالا کاری ندارم
صورت سوال فقط گفته هزینه دو عدد aبیتی,bبیتی میشه ماکسشون!!..نگفته چجوری جمع کنی!!
شما nتا ۱داشته باشه بصورت ۲تا ۲تا جدا کن جمع کن!!یعنی هربار دو عدد ۱بیتی که شکل ی درخت پر دودویی میشه!!
حالا چون همه nتا عدد ۱هستن ممکنه حاصل جمع بیت اضافه تولید کنه ..اینجور نیس که همیشه همون ۱بیت بمونه!!!!!!!!!...ک بگیم nتا عمل با هزینه ۱میشه !!
اینجور ک من میگم هربار ی بیت داره اضافه میشه چون عمق درختم log nهست میشه جمع از ۱تا logn!!ک میشه از مرتبه [tex]O(\log\: n)[/tex]
اگه جمع n تا یک رو به صورت تقسیم و حل بنیویسیم، اینی که شما میگین جمع یک تا logn میشه برای یک مسیر درخت از ریشه تا برگ، در صورتی این جواب درسته که با هربار جمع کردن یک بیت اضافه نشه و همه ی جمع ها از مرتبه ۱ باشند، ولی چون اینطوری نیست و در هر سطح درخت مرتبه الگوریتم یک عدد اضافه میشه اگر شما این درخت رو برای یه عدد دلخواه مثل ۱۶ رسم کنید خواهید دید که مجموع اعمال اصلی برابر میشه [tex]\sum^{\log n}_{i=1}\frac{n}{2^i}i[/tex] که مرتبش nlogn هستش، همونطوری که تو پست اولتون گفتید،
حالا کلن هم به نظرم اگه اینطوری فکر کنیم که نتیجه هر جمع با قبلیش جمع نمیشه و فقط همه ی بیت های کنار هم رو با هم جمع میکنیم ، میشه توجیه واسه این جواب سنجش پیدا کرد. شایدم جواب غلط باشه یا من اشتباه می کنم
nlogn رو می فهمم چی میگین!
ولی تو حداقلش وقتی این حل پارسه رو دیدم شک کردم!!
یعنی شما میگید غلطه؟؟
(۰۳ بهمن ۱۳۹۳ ۰۷:۴۴ ب.ظ)shamim_70 نوشته شده توسط: nlogn رو می فهمم چی میگین!آره این غلطه، اصلا این درختی که خودش واسه بهترین حالت کشیده رو اشتباه مرتبه زمانیشو حساب کرده
ولی تو حداقلش وقتی این حل پارسه رو دیدم شک کردم!!
یعنی شما میگید غلطه؟؟
(۰۴ بهمن ۱۳۹۳ ۱۰:۴۸ ق.ظ)farhad_vr32 نوشته شده توسط:اره مرتبه زمانیش اشتباهه،.(03 بهمن ۱۳۹۳ ۰۷:۴۴ ب.ظ)shamim_70 نوشته شده توسط: nlogn رو می فهمم چی میگین!آره این غلطه، اصلا این درختی که خودش واسه بهترین حالت کشیده رو اشتباه مرتبه زمانیشو حساب کرده
ولی تو حداقلش وقتی این حل پارسه رو دیدم شک کردم!!
یعنی شما میگید غلطه؟؟
اونی ک شما میگید درست تره،
مرسی
(۰۵ بهمن ۱۳۹۳ ۱۱:۳۶ ق.ظ)shamim_70 نوشته شده توسط: اره مرتبه زمانیش اشتباهه،.خواهش می کنم
اونی ک شما میگید درست تره،
مرسی