سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟
[attachment=14791]
[attachment=14792]
(۳۰ دى ۱۳۹۲ ۰۷:۳۹ ب.ظ)*afsoon* نوشته شده توسط: سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟
سوال ۴۲
واسه 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 نوشته شده توسط:(30 دى ۱۳۹۲ ۰۷:۳۹ ب.ظ)*afsoon* نوشته شده توسط: سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟
سوال ۴۲
واسه 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]
سری هندسی.
مرسی
ولی من منظورتونو از پارتیشن متوجه نمیشم!!!
(۰۱ بهمن ۱۳۹۲ ۱۲:۴۲ ق.ظ)*afsoon* نوشته شده توسط:(30 دى ۱۳۹۲ ۰۸:۱۶ ب.ظ)Riemann نوشته شده توسط:مرسی(30 دى ۱۳۹۲ ۰۷:۳۹ ب.ظ)*afsoon* نوشته شده توسط: سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟
سوال ۴۲
واسه 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]
سری هندسی.
ولی من منظورتونو از پارتیشن متوجه نمیشم!!!
این روال کار الگوریتم هستش که یه عنصر رو انتخاب میکنه و بعدش اونایی که از اون بزرگتر هستن رو میزاره سمت راستش و اونایی که از اون کوچیک تر هستن رو میزاره سمت چپش. و به همین ترتیب بازگشتی ادامه پیدا میکنه. این در واقع الگوریتم select هستش که مثه مرتب سازی سریع کار میکنه.