تالار گفتمان مانشت

سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟
[attachment=14791]
[attachment=14792]

(30 دى 1392 07:39 ب.ظ)*afsoon* نوشته شده توسط: [ -> ]سلام
سوال ۳۹و۴۲ ساختمان داده اشکال دارم
کسی میتونه برام توضیح بده ؟

سوال 42
واسه 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]
سری هندسی.

(30 دى 1392 08:16 ب.ظ)Riemann نوشته شده توسط: [ -> ]

(30 دى 1392 07:39 ب.ظ)*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]
سری هندسی.

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

(01 بهمن 1392 12:42 ق.ظ)*afsoon* نوشته شده توسط: [ -> ]

(30 دى 1392 08:16 ب.ظ)Riemann نوشته شده توسط: [ -> ]

(30 دى 1392 07:39 ب.ظ)*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 هستش که مثه مرتب سازی سریع کار میکنه.