واسه s1 ما میخواهایم k عنصر اول رو بدست میاریم یه راه حلش اینه که ما عنصر k ام رو توی O n بدست میاریم و بعد آرایه رو حول اون عنصر پارتیشن میکنیم و بعد سمت راست اون عنصر k ام رو مرت میکنیم که مرتبه کلش میشه [tex]O(n k\lg k)[/tex]
واسه s2 ما میتونیم اول ما عنصر میانه رو توی n بدست میاریم حالا حول این عنصر پارتیشن میکنیم سایز حالا توی سمت چپ این عنصر دوباره همین کار رو میکنیم و توی n/2 میانه این رو که میشه عنصر n/4 و یا چارک اول رو بدست میاریم و داریم کل هزینه برابر با:[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} \dots = n[/tex]
سری هندسی.

(۰۸ بهمن ۱۳۹۲ ۰۵:۴۰ ب.ظ)Riemann نوشته شده توسط:  واسه s1 ما میخواهایم k عنصر اول رو بدست میاریم یه راه حلش اینه که ما عنصر k ام رو توی O n بدست میاریم و بعد آرایه رو حول اون عنصر پارتیشن میکنیم و بعد سمت راست اون عنصر k ام رو مرت میکنیم که مرتبه کلش میشه [tex]O(n k\lg k)[/tex]
واسه s2 ما میتونیم اول ما عنصر میانه رو توی n بدست میاریم حالا حول این عنصر پارتیشن میکنیم سایز حالا توی سمت چپ این عنصر دوباره همین کار رو میکنیم و توی n/2 میانه این رو که میشه عنصر n/4 و یا چارک اول رو بدست میاریم و داریم کل هزینه برابر با:[tex]n \frac{n}{2} \frac{n}{4} \frac{n}{8} \dots = n[/tex]
سری هندسی.

متشکرم از توضیح کاملتون
یه سوال دیگه، ما نمی تونیم همون s1 هم در (O(n بدست بیاریم؟ تک تک اعضاش رو در (O(n نمیشه بدست اورد؟

خب این مرتبش میشه فکر کم kn که خوب نیست.

(۰۸ بهمن ۱۳۹۲ ۰۵:۵۳ ب.ظ)Riemann نوشته شده توسط:  خب این مرتبش میشه فکر کم kn که خوب نیست.

یعنی هزینه اش از هزینه جواب تست بیشتر میشه؟ یا اصلا چنین راه حلی غلطه؟

(۰۸ بهمن ۱۳۹۲ ۰۵:۵۷ ب.ظ)fulgent نوشته شده توسط:  یعنی هزینه اش از هزینه جواب تست بیشتر میشه؟ یا اصلا چنین راه حلی غلطه؟

راه حل درسته هزینش بهینه نیس

دوست عزیز مگه ۱+(۱/۲)+ (۱/۴)+ (۱/۸)+ ... نمی‌شه log n پس چرا جواب نشده باn بیرونی هم ضربدر می‌شه : nlog n

(۱۴ بهمن ۱۳۹۲ ۰۶:۰۹ ب.ظ)Mehrdad7soft نوشته شده توسط:  دوست عزیز مگه ۱+(۱/۲)+ (۱/۴)+ (۱/۸)+ ... نمی‌شه log n پس چرا جواب نشده باn بیرونی هم ضربدر می‌شه : nlog n

نخیر ۱+۱/۲+۱/۳+۱/۴+۱/۵+.... میشه log n
ولی سری ۱ + ۱/۲+ ۱/۴ +۱/۸ تصاعد هندسی است با قدر نسبت ۱/۲

(۱۴ بهمن ۱۳۹۲ ۰۶:۱۳ ب.ظ)izadan11 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۶:۰۹ ب.ظ)Mehrdad7soft نوشته شده توسط:  دوست عزیز مگه ۱+(۱/۲)+ (۱/۴)+ (۱/۸)+ ... نمی‌شه log n پس چرا جواب نشده باn بیرونی هم ضربدر می‌شه : nlog n

نخیر ۱+۱/۲+۱/۳+۱/۴+۱/۵+.... میشه log n
ولی سری ۱ + ۱/۲+ ۱/۴ +۱/۸ تصاعد هندسی است با قدر نسبت ۱/۲

خدا خیرت بده جوون. ما که پیر شدیم و چشمامون سوی دیدن این عددها رو نداره
بدجور بعضی چیزارو نمیبینم.

(۱۴ بهمن ۱۳۹۲ ۰۶:۲۳ ب.ظ)masoud67 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۶:۱۳ ب.ظ)izadan11 نوشته شده توسط:  

(14 بهمن ۱۳۹۲ ۰۶:۰۹ ب.ظ)Mehrdad7soft نوشته شده توسط:  دوست عزیز مگه ۱+(۱/۲)+ (۱/۴)+ (۱/۸)+ ... نمی‌شه log n پس چرا جواب نشده باn بیرونی هم ضربدر می‌شه : nlog n

نخیر ۱+۱/۲+۱/۳+۱/۴+۱/۵+.... میشه log n
ولی سری ۱ + ۱/۲+ ۱/۴ +۱/۸ تصاعد هندسی است با قدر نسبت ۱/۲

خدا خیرت بده جوون. ما که پیر شدیم و چشمامون سوی دیدن این عددها رو نداره
بدجور بعضی چیزارو نمیبینم.

ااه راست میگیا گویا از وقتی‌ دفترچه اعزامم اومده عقل از سرم پریده

دمت گرم چشم آلبالو گیلاس میدید

الان یعنی سری logn اینه؟؟؟؟؟
۱+۱/۲+۱/۳+۱/۴+۱/۵+.....

این tapatalk قاطی کرده. جوابش گزینه ۴ میشه؟!
یا ۲؟!

Sent from my SM-T210R using Tapatalk

(۱۴ بهمن ۱۳۹۲ ۰۶:۵۱ ب.ظ)hoomanab نوشته شده توسط:  این tapatalk قاطی کرده. جوابش گزینه ۴ میشه؟!
یا ۲؟!

Sent from my SM-T210R using Tapatalk

گزینه ۲ میشه