پاورپوینت تحلیل الگوریتم ها (pptx) 36 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 36 اسلاید

قسمتی از متن PowerPoint (.pptx) :

بنام خدا 2 درس: ساختمان داده مبحث: تحلیل الگوریتم ها مثال: مرتب سازي (Sorting) مرتب كردن عناصر يك آرايه با n عنصر به ترتيب صعودي ( a[0] <= a[1] <= … <= a[n-1] ). 8, 6, 9, 4, 3  3, 4, 6, 8, 9 Insertion Sort با يك زيرمجموعه به اندازه 1 شروع كن هر بار عنصر بعدي از عناصر مرتب نشده را به زيرمجموعه مرتب شده اضافه كن (insert) Insert كردن 5 به 3,6,9,14 مثال: مرتب كردن با insertion Sort Original List After pass 1 After pass 2 After pass 3 After pass 4 After pass 5 Sorted Unsorted الگوريتم InsertionSort InsertionSort for k=1 to length(A)-1 key = A[k] i = k - 1 while (i >= 0 and A[i] > key) A[i+1] = A[i] i = i - 1 A[i+1] = key هزينه تعداد دفعات اجرا cost  times executed c1  n c2  n-1 c3  n-1 c4  tk c5  (tk-1) c6  (tk-1) c7  n-1 n k=2 n k=2 n k=2 tk: وابسته به ترتيب عناصر بهترين حالت: tk=1 بدترين حالت: tk=k حالت متوسط: تركيبهاي مختلف ممكن مقايسه الگوريتمهاي مختلف 1000*1000=106 n=lg2106 =20 20/10=2