پاورپوینت تحلیل الگوریتم ها (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
