(۰۴ مهر ۱۳۹۳ ۰۹:۴۱ ب.ظ)directline نوشته شده توسط: (04 مهر ۱۳۹۳ ۰۹:۰۸ ب.ظ)m@hboobe نوشته شده توسط: n را ریشه قرار بدید و درخت رسم کنید!هر بار مقدار n در یک سمت درخت یک واحد کم میشه و در سمت دیگه نصف میشه همین طور هر گره جدید رو ادامه میدیم....
حد بالای این تایع در سمتی بدست میاد که n-1 انجام میشه پس مرتبه این تابع از O(n2) است.
قبول اما شما چطور جمع سطوح درخت رو انجام دادید؟ اخه روند خاصی براش به دست نمیاد!
فکر کنم استدلال شما اینطور که ارتفاع که N میشه تو هر سطح هم که یک ضریبی از N داریم پس میشه N^2 درسته؟ اگر اینطوره از کجا میدونید سیگما سطوح رو حساب کنید به N^3 نمیرسه؟
درسته حق با شماست اگر بخواهیم بطور دقیق درخت رسم کنید چنین چیزی به نتیجه جالبی نمیرسیم
ولی حداقل با همین روش که کاملا هم درست نیست (اگر دقت کنید جلوی جمله رسم درختم علامت تعجب گذاشتم

) متوجه میشیم که اگر بخواهیم محاسبه رو با اون قسمت از تایع که هر بار یک واحد کم میکنه انجام بدیم ارتفاع بیشتری داریم (با توجه به صحبتهای سایر بچه ها = دیر تر به یک نزدیک میشه!) پس اون بخش موثر در حل هست
من خودم اولین بار که به این مساله برخورد کردم اینجور درنظر گرفتم که ممکنه هر بار یه بخش از این تابع اتفاق بیفته با n-1 مرتبه که
Theta(n2) شد و با n/2 از طریق مستر شد
Theta(n) که گفتم کران بالای حل میشه
O(n2) 
امیدوارم که با توضیحاتم گیج نشده باشید
موفق باشین