(۳۰ دى ۱۳۹۲ ۰۸:۱۶ ب.ظ)Riemann نوشته شده توسط:  

(30 دى ۱۳۹۲ ۰۷:۳۹ ب.ظ)*afsoon* نوشته شده توسط:  سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟

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

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

(30 دى ۱۳۹۲ ۰۸:۱۶ ب.ظ)Riemann نوشته شده توسط:  

(30 دى ۱۳۹۲ ۰۷:۳۹ ب.ظ)*afsoon* نوشته شده توسط:  سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟

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

مرسی
ولی من منظورتونو از پارتیشن متوجه نمیشم!!!