زمان کنونی: ۱۰ فروردین ۱۴۰۳, ۱۱:۰۳ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

ارسال:
  

tarane1992 پرسیده:

هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

سلام

جواب گزینه ۱ هست.

این سوالو اصلا نمیفهمم یکی برام توضیح بده منم متوجه بشم ممنون میشمShy





مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
نقل قول این ارسال در یک پاسخ

۳
ارسال:
  

rad.bahar پاسخ داده:

RE: هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

اول شکل ۱ ضمیمه را دانلود کنید همین طور در شکل نشان داده شده در اجرای عملیات مرتب سازی ادغامی روابط نشان داده شده بین طول هر صف و ارتفاع درخت از ریشه تا مکان آن صف ارتباطی وجود دارد. در شکل n=8 می باشد . در هر مرحله اگر طول هر صف v باشد و ارتفاع از ریشه درخت تا مکان صف های ان مرحله w باشد داریم
(v) ضربدر ( تعداد صف به طول v ) = n
( تعداد صف به طول v ) = [tex]2^{w}[/tex]
از دو رابطه بالا نتیجه می شود
[tex]2^{w}\times v=n[/tex]
حالا که این مقدمه گفته شد بریم سراغ صورت سوال
فرض کنید b توانی از ۲ باشد شکل ۲ ضمیمه شده را دانلود کنید همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.
ولی اگر طول صف b یا بیشتر باشد هزینه هر مرحله ادغام برابر o(n می باشد برای اثبات این موضوع فرض کنید در مرحله ای هستید که طول تمام صف ها k می باشد و تعداد کل این صف ها z می باشد حال بر طبق الگوریتم مرتب سازی ادغامی هر دو صف مرتب با طول k برای تولید صف مرتب با طول ۲k در هم ادغام می شوند.
می دانیم هزینه ترکیب دو صف مرتب (تعداد مقایسه ها) به طول m وn حداکثر برابر m+n-1 می باشد
پس هزینه تولید هر صف با طول ۲k از دو صف با طول k برابر ۲k-1 می باشد و چون در کل zتا صف با طول k داشتیم پس از اجرای الگوریتم ترکیب کردن صف ها، به تعداد z/2 صف با طول ۲k داریم پس در کل هزینه این مرحله (تعداد کل مقایسه های صورت گرفته شده) برابر است با
( ۲k-1)(z/2)
همانطور که در بالا درباره شکل ۱ و اولین معادله آن گفته شد رابطه ضرب kz=n برقرار است. پس در کل هزینه هر مرجله برابر است با
[tex]O((2k-1)(\frac{z}{2}))= O(kz)=O(n)[/tex]
خوب جالا که هزینه هر مرجله را می دانیم برای حساب هزینه کل باید تعداد مرحله ها را بدانیم تا با ضرب کردن تعداد مرحله در هزینه هر مرحله هزینه کل را به دست آوریم. و همان طور در شکل ۲ نبز مشهود است تعداد مرحله هایی که هزینه ان مرحله ها o(n) می باشد برابر باارتفاع درخت ار ریشه تا مکان صف ها با طول b می باشد. که برای محاسبه این طول از سومین فرمولی که درباره شکل ۱ گفته شد استفاده می کنیم. تعداد مرحله ها را با r نشان می دهیم.
[tex]2^{r}\times b=n =>r =log(\frac{n}{b})[/tex]
پس هزینه کل برابر است با
[tex]O(log(\frac{n}{b})O(n))=O(nlog(\frac{n}{b})[/tex]

در بالا فرض کردیم b توانی از ۲ باشد حتی اگر b توانی از ۲ نیاشد با توجه به توضیحات گفته شده گ۱ درست هست


فایل‌(های) پیوست شده


مشاهده‌ی وب‌سایت کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

دوستان کمکم کنید من این سوالو متوجه نمیشم .Shy
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

tarane1992 پاسخ داده:

RE: هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

بسیار ممنونم واقعا شرمنده ام میدونم برای جواب دادن به این سوال خیلی از وقتتون گرفته شده منو ببخشید

خیلی خیلی خیلی توضیحتون کامل بود من فقط یه جایی رو متوجه نشدم همون اوایل که گفتید((همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.))
سوال من اینه که سوال گفته که وقتی j-i<<b باشد برابر صفر در غیر اینصورت هزینه یک میشود. یعنی زمانی که میخواییم دو عنصر رو با هم ادغام کنیم اگر اختلافشون از b کمتر یا مساوی بشه صفر میشه ولی اگرj-i>b هزینه یک میشود خوب شما دارید میگید b/2 یا کمتر باشد برابر O(1 مشه من این جملتونو متوجه نمیشم چطور استدلال کردید؟؟

اگر بگید ممنون میشم.Shy
نقل قول این ارسال در یک پاسخ

ارسال:
  

rad.bahar پاسخ داده:

RE: هزینه مرتب سازی ادغامی(کامپیوتر ۸۹)

(۲۰ آذر ۱۳۹۲ ۰۸:۱۸ ب.ظ)tarane1992 نوشته شده توسط:  بسیار ممنونم واقعا شرمنده ام میدونم برای جواب دادن به این سوال خیلی از وقتتون گرفته شده منو ببخشید

خیلی خیلی خیلی توضیحتون کامل بود من فقط یه جایی رو متوجه نشدم همون اوایل که گفتید((همان طور که در صورت سوال کفته و در شکل نشان داده شده هزینه ادغام هر دو صف از زمانی که طول هر صف b/2 یا کمتر باشد برابر O(1 می باشد زیرا می دانیم حداکثر فاصله (از نظر اختلاف اندیس) بین دو صفی که باید با هم ترکیب شوند کمتر از b می باشد پس هزینه هر مرجله که دارای صف هایی با طول b/2 یا کمتر باشد برابر O(1 می باشد.))
سوال من اینه که سوال گفته که وقتی j-i<<b باشد برابر صفر در غیر اینصورت هزینه یک میشود. یعنی زمانی که میخواییم دو عنصر رو با هم ادغام کنیم اگر اختلافشون از b کمتر یا مساوی بشه صفر میشه ولی اگرj-i>b هزینه یک میشود خوب شما دارید میگید b/2 یا کمتر باشد برابر O(1 مشه من این جملتونو متوجه نمیشم چطور استدلال کردید؟؟

اگر بگید ممنون میشم.Shy
این را قبول داریم که هرینه ترکیب دو صف که طول هر صف b/2 یا کمتر هست صفر می باشد پس یعنی هزینه برابر یک مقدار ثابت (در اینجا صفر) می باشد. از نظر مجانبی اگر k یک عدد ثابت باشد داریم
O(k)=O(1
مشاهده‌ی وب‌سایت کاربر یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  پکیج آموزشی طراحی وب + فارسی سازی وردپرس + سئو Happiness.72 ۶ ۶,۲۸۶ ۱۸ بهمن ۱۳۹۹ ۰۱:۱۵ ب.ظ
آخرین ارسال: saqarmoshtaq
Heart هزینه عشق واقعی چقدر است aatwo ۵ ۵,۳۰۹ ۱۳ بهمن ۱۳۹۹ ۱۰:۱۴ ب.ظ
آخرین ارسال: ghaderZ
  مرتب سازی سریع تصادفی چیست؟ Xzrix ۰ ۱,۳۶۸ ۱۴ آذر ۱۳۹۹ ۰۷:۲۲ ب.ظ
آخرین ارسال: Xzrix
  شبیه سازی مقاله Q-Learning kadoos ۱۶ ۱۵,۱۴۵ ۲۵ آبان ۱۳۹۹ ۰۹:۱۹ ب.ظ
آخرین ارسال: nasim.nasim۱
  کتاب شبیه سازی آمنت omnet++ berkeley ۱ ۳,۸۳۷ ۰۴ اردیبهشت ۱۳۹۹ ۱۲:۳۳ ق.ظ
آخرین ارسال: محمد رستمی
  چگونگی پرداخت هزینه ثبت نام تیزهوشان ۹۹-۱۴۰۰ edumoshaver1 ۰ ۱,۸۳۹ ۱۲ اسفند ۱۳۹۸ ۰۵:۰۲ ب.ظ
آخرین ارسال: edumoshaver1
  سئو چیست؟ - سئو - بهینه سازی سایت msnmsn ۲ ۲۴ ۲۳ آبان ۱۳۹۸ ۰۱:۱۳ ب.ظ
آخرین ارسال: xiaomi
  مجموعه آموزش تصویری ابزار شبیه سازی و بررسی پروتکل امنیتی اسکایتر net work ۰ ۲,۳۱۷ ۲۲ فروردین ۱۳۹۸ ۰۳:۲۵ ب.ظ
آخرین ارسال: net work
  برگ برگ سازی Sanazzz ۱ ۱,۹۰۲ ۱۳ فروردین ۱۳۹۸ ۰۸:۱۸ ب.ظ
آخرین ارسال: Sanazzz
  راهنمایی برای انتخاب موضوع قابل پیاده سازی در زمینه بیگ دیتا برای پایان نامه one hacker alone ۱ ۲,۹۸۸ ۱۸ بهمن ۱۳۹۷ ۰۶:۳۶ ب.ظ
آخرین ارسال: Happiness.72

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close