فایل های مشابه شاید از این ها هم خوشتان بیاید !!!!
توضیحات محصول دانلود پاورپوینت آنالیز مرتب سازی با تقسیم تصادفی (کد13535)
دانلود پاورپوینت آنالیز مرتب سازی با تقسیم تصادفی
\nمرتب سازی سریع Quicksort
\n\n عنوان های پاورپوینت :
\n\nآنالیز مرتب سازی با تقسیم تصادفی
\nمرتب سازی سریع Quicksort
\nQuicksort
\nتقسیم و حل
\nتقسیم
\nمثال
\nشبه کد الگوریتم مرتب سازی
\nآنالیز الگوریتم
\nبدترین حالات quicksort
\nدرخت هزینه بدترین حالت
\nبهترین حالت
\n10% 90%
\nحالتی دیگر
\nRandomized Quicksort
\nشبه کد الگوریتم تقسیم تصادفی
\nآنالیز مرتب سازی با تقسیم تصادفی
\nبحث و بررسی
\n\n \n\n \n\n
\n\nقسمت ها و تکه های اتفاقی از فایل\n\n \n\nQuicksort\n\nHoare در سال 1962 پیشنهاد کرده است\n\nاز روش تقسیم و حل (Divide & Conquer) استفاده می کند\n\nآرایه را به صورت “در جا” (In Place)مرتب می کند\n\nشبیه مرتب سازی درجی(Insertion Sort) است.\n\nبرخلاف (Merge Sort ) به حافظه اضافی نیاز ندارد.\n\nپیاده سازی های سریعی که برای آن ارائه شده، باعث بکارگیری وسیع آن در عمل شده است.\n\nتقسیم و حل\n\nتقسیم:یک عضو مثل x از آرایه را انتخاب کرده و آرایه را طوری به دو بخش طوری تقسیم می کنیم که یک بخش آن از x کوچکتر و بخش دیگر از x بزرگتر باشند.\n\nآنالیز الگوریتم\n\nفرض کنید تمام اعضای آرایه غیر تکراری هستند.\n\nدر عمل معمولا روشهای مناسبتری برای تقسیم آرایه هایی که اعضای تکراری دارند، استفاده می شود\n\nفرض کنید (T(n هزینه مرتب سازی آرایه ای به طول n با استفاده ازاین الگوریتم در بدترین حالت باشد.\n\nمعمولا بهترین حالت الگوریتمها را در نظر نمی گیریم اما برای مرتب سازی سریع این حالت را نیز بررسی می کنیم.\n\nبدترین حالات quicksort\n\nآرایه از قبل مرتب شده باشد.\n\nتقسیم حول مقدار مینیمم یا ماکزیمم صورت گیرد.\n\nیکی از دو بخش بدست آمده از تقسیم، هیچ عضوی نداشته باشد.\n\n(T(n) = T(0) + T(n-1) + Θ(n) = Θ(1) + T(n -1) + Θ(n) = T(n-1) + Θ(n) n + n-1+ …+1 = Θ(n2\n\nبهترین حالت\n\nدر بهترین حالت، دو بخش تقسیم شده تقریبا هم اندازه هستند و اندازه مساله در هر بار تقسیم نصف می شود:\n\n(T(n) = 2T(n/2) + Θ(n) Θ(n log n) (mergesort\n\nسوال: اگر تقسیم طوری صورت بگیرد که 90% اعضای آرایه در یک بخش و %10 در بخش دیگر قرار بگیرند، هزینه الگوریم چگونه خواهد بود؟\n\nT(n) = T(n/10) + T(9n/10)+ Θ(n)\n\nRandomized Quicksort\n\nعمل تقسیم نقش اصلی را در تعیین هزینه الگوریتم دارد\n\nچگونه تقسیم متوازنی انجام دهیم؟\n\nیا، چگونه می توانیم امیدوار باشیم اغلب تقسیم ها متوازن هستند؟\n\nانتخاب تصادفی عضو نشانگر pivot\n\nزمان اجرا مستقل از مقادیر و توزیع ورودیهاست\n\nهیچ ورودی خاصی سبب شکل گیری بدترین حالت الگوریتم نمی شود\n\nاحتمال وقوع بدترین حالت تنها به مولد اعداد (شبه) تصادفی بستگی دارد\n\nآنالیز مرتب سازی با تقسیم تصادفی\n\nبا انتخاب تصادفی نشانگر؛ آرایه ای به طول n ممکن است به صورت {0:n-1} ; {1,n-2}; …; {n/2 :n/2} تقسیم شود.\n\nفرض کنید الگوریتم تقسیم دو بخش k:n-k-1 را تولید می کند که در آن k=0,1,…, n-1 است.\n\nمتغیر تصادفی Xk را چنین تعریف می کنیم:\n\nXk=1 اگر طول دوبخش k:n-k-1 باشد؛ در غیر اینصورت، Xk =0.\n\nXk را متغیر تصادفی نشانگر (Indicator Random Variable)می گویند.\n\nE[Xk] = P(Xk =1) = 1/n\n\nبحث و بررسی\n\nالگوریتم quicksort تصادفی، از نظر هزینه با mergesort هم رتبه است.\n\nچون نیازی به حافظه اضافی ندارد، معمولا انتخاب اول برای مرتب سازی است.\n\nدر عمل این الگوریتم بین 3 تا 9 برابر سریعتر از mergesort اجرا می شود.\n\n \n\n \n\n30 تا 70 درصد پروژه | پاورپوینت | سمینار | طرح های کارآفرینی و توجیهی | پایان-نامه | پی دی اف مقاله ( کتاب ) | نقشه | پلان طراحی | های آماده به صورت رایگان میباشد ( word | pdf | docx | doc )
