متوجه منظورتون نمیشم
یعنی چی بیت کناریش؟
بیت کناری مگه وجود داره؟
میگه ۱ بیتی

---

آها تازه متوجه سوال شدم ‎
بله حق با شماست

(۳۰ دى ۱۳۹۳ ۱۱:۵۲ ق.ظ)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 میشه!!

صورت سوال فقط گفته هزینه دو عدد aبیتی,bبیتی میشه ماکسشون!!..نگفته چجوری جمع کنی!!
شما nتا ۱داشته باشه بصورت ۲تا ۲تا جدا کن جمع کن!!یعنی هربار دو عدد ۱بیتی که شکل ی درخت پر دودویی میشه!!
حالا چون همه nتا عدد ۱هستن ممکنه حاصل جمع بیت اضافه تولید کنه ..اینجور نیس که همیشه همون ۱بیت بمونه!!!!!!!!!...ک بگیم nتا عمل با هزینه ۱میشه !!
اینجور ک من میگم هربار ی بیت داره اضافه میشه چون عمق درختم log nهست میشه جمع از ۱تا logn!!ک میشه از مرتبه [tex]O(\log\: n)[/tex]

شما حداقل رو که خودتون گفتین میشه مرتبه n ، اونو حالا کاری ندارم
اگه جمع 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 نوشته شده توسط:  اره مرتبه زمانیش اشتباهه،.
اونی ک شما میگید درست تره،
مرسی

خواهش می کنم