درود
لطفا راهنمایی کنید
(۰۸ بهمن ۱۳۹۲ ۰۷:۲۴ ب.ظ)tayebe68 نوشته شده توسط: درود
لطفا راهنمایی کنید
شما راه حل ۵ تاییش رو که بلد باشی ۳ تاییش رو هم میتونی حل کنی، حلش طول میشکه.
کسی بلد هست چه با سه تایی چه ۵ تایی ی توضیح بده ممنون میشم
توضیح این فرمول اینه که ما گروه هامون رو به دسته های ۵ تایی تقسیم بندی میکنیم و میانه ها رو به ازای هر گروه به دست میاریم.حالا میانه این میانه ها رو هم به دست میاریم و اسمش رو x میذاریم.حالا ببین قبول داری حداقل نصف میانه ها از x بزرگترن و نصفی هم کوچکتر چرا؟ چون x میانه میانه هاست درسته؟
پس تا الان [tex]\frac{1}{2}\ast\frac{n}{5}[/tex] عناصر از x بزرگتر هستند. (شما سقف رو بزای تقسیم در نظر بگیر)حالا این گروه هایی که میانشون از x( میانه میانه ها ) بزرگتره رو در نظر بگیر قبول داری که توی اون گروه ها دو عنصر دیگه هم هست که از میانه اون گروه ها بزرگتره( ببین چون گروه ها رو به دسته های ۵ تایی تقسیم کردیم پس وقتی مرتبشون کردیم میانشون میشه عنصر سوم خب؟ حالا فرض کن این یکی از همون گروه هایی هست که میانش از x بزرگتره پس عناصر ۴ و ۵ هم تو این گروه مقدارشون از x بزرگتره درسته؟ پس جمعا شد ۳ عنصر که مقدارشون از x بزرگتره )و گفتیم تعداد این گروه ها که این شرایط رو دارن میشه [tex]\frac{n}{5}\ast\frac{1}{2}[/tex] ولی گروه اخر این شرایط رو نداره چون فرض کن کلا ۲۷ داده داریم گروه اخر اون وقت ۲ عضو داره پس از این قاعده مستثناس و خود گروهی که x عضوشه چون از خودش که بزرگتر نیست پس از مقدار [tex]\frac{n}{5}\ast\frac{1}{2}[/tex] عدد ۲ رو کم میکنم چون ۲ گروه شامل این گروه ها نمیشن و کل این عبارت رو در ۳ ضرب میکنم چون تو هر کدوم از این گروه ها [tex]((\frac{1}{2}\ast\frac{n}{5})-2)[/tex] که به دست اوردیم ۳ عضو هست که از x بزرگتره پس کل اون عبارت رو در ۳ ضرب کردیم. [tex]3((\frac{1}{2}\ast\frac{n}{5})-2)[/tex].پس تعداد عناصری که از x بزرگترن شد [tex]3((\frac{1}{2}\ast\frac{n}{5})-2)[/tex] و بدترین حالت اینه که ما روی قسمت دیگه الگوریتم رو پیاده کنیم یعنی:
[tex]n-3((\frac{1}{2}\ast\frac{n}{5})-2)=\frac{7n}{10}-6[/tex]
پس زمان اجرای کل شد:
[tex]T(n)=T(\frac{n}{5}) T(\frac{7n}{10} 6) \theta(n)[/tex]
[tex]\theta(n)[/tex] : زمان پیدا کردن میانه هر گروه
[tex]T(\frac{n}{5})[/tex] : پیدا کردن میانه میانه
[tex]T(\frac{7n}{10} 6)[/tex] : پیدا کردن عنصر مورد نظر
امیدوارم خیلی بد نشده باشه!!انگاری خیلی پیچیده شد!!احتیاج به توضیح بیشتر بود بگید
(۲۹ دى ۱۳۹۳ ۱۲:۵۳ ق.ظ)miladcr7 نوشته شده توسط: توضیح این فرمول اینه که ما گروه هامون رو به دسته های ۵ تایی تقسیم بندی میکنیم و میانه ها رو به ازای هر گروه به دست میاریم.حالا میانه این میانه ها رو هم به دست میاریم و اسمش رو x میذاریم.حالا ببین قبول داری حداقل نصف میانه ها از x بزرگترن و نصفی هم کوچکتر چرا؟ چون x میانه میانه هاست درسته؟مرسییی
پس تا الان ۱/۲*n/5 عناصر از x بزرگتر هستند. (شما سقف رو بزای تقسیم در نظر بگیر)حالا این گروه هایی که میانشون از x( میانه میانه ها ) بزرگتره رو در نظر بگیر قبول داری که توی اون گروه ها دو عنصر دیگه هم هست که از میانه اون گروه ها بزرگتره( ببین چون گروه ها رو به دسته های ۵ تایی تقسیم کردیم پس وقتی مرتبشون کردیم میانشون میشه عنصر سوم خب؟ حالا فرض کن این یکی از همون گروه هایی هست که میانش از x بزرگتره پس عناصر ۴ و ۵ هم تو این گروه مقدارشون از x بزرگتره درسته؟ پس جمعا شد ۳ عنصر که مقدارشون از x بزرگتره )و گفتیم تعداد این گروه ها که این شرایط رو دارن میشه ۱/۲*n/5 ولی گروه اخر این شرایط رو نداره چون فرض کن کلا ۲۷ داده داریم گروه اخر اون وقت ۲ عضو داره پس از این قاعده مستثناس و خود گروهی که x عضوشه چون از خودش که بزرگتر نیست پس از مقدار n/5*1/2 عدد ۲ رو کم میکنم چون ۲ گروه شامل این گروه ها نمیشن و کل این عبارت رو در ۳ ضرب میکنم چون تو هر کدوم از این گروه ها *۱/۲(n/2-2) که به دست اوردیم ۳ عضو هست که از x بزرگتره پس کل اون عبارت رو در ۳ ضرب کردیم. خب تموم شد.اگه بد توضیح دادم بگید تا واضح تر توضیح بدم براتون:
من تقریبا همین توضیخات رو کتاب قدسی خوندم نفهمیدم!! ولی الان کاملا متوجه شدم ممنون
