ساختمان داده‌ها و الگوریتم
رشته علوم کامپیوتر
ناصر آیت
ساختمان داده روشی است برای معرفی و دستکاری داده
و کلیه برنامه های معرفی داده
برای معرفی داده نیازمند یک الگوریتم میباشد.
روش های طراحی الگوریتم نیازمند پیشرفت برنامه هایی است که برای نگهداری داده است.
در علوم کامپیوتر مطالعه ساختمان داده ها مهم وضروری میبا شد.
پاورپوینت درمورد ساختمان داده‌ها و الگوریتم
Perequisites
C++
پیچیدگی
Big oh , theta and omega notation
Sorting
ترتیب زیر را در نظر بگیرید:
a[0],a[1],…, a[n-1]
پس از مرتب سازی صعودی داریم:
a[0] <=a[1] <= ….<=a[n-1]
example:8,6,9,4,3 => 3,4,6,8,9
Sort metods
Insertion sort
Bubble sort
Selection sort
Count sort
Shaker sort
Shell sort
Heap sort
Merge sort
Quick sort
پاورپوینت درمورد ساختمان داده‌ها و الگوریتم
اضافه کردن یکinsert an element
لیست ترتیبی زیر را در نظر بگیرید:
input: ۳, ۶, ۹, ۱۴
عنصر ۵ را به لیست فوق اضافه کنید.
output: 3, 5, 6, 9, 14
Insert An Element
۳, ۶, ۹, ۱۴ insert ۵
عدد ۵ را با آخرین عنصر لیست مقایسه کنید .
Shift 14 right to get ۳, ۶, ۹, , ۱۴
Shift ۹ right to get ۳, ۶, , ۹, ۱۴
Shift ۶ right to get ۳, , ۶, ۹, ۱۴
با اضافه کردن ۵ خروجی:
Output: ۳, ۵, ۶, ۹, ۱۴
Insert An Element
// insert into a[0:i-1]
Int j;
For (j=i-1 ; j>=0 && t <a[ j] ;j–)
A[ j+1] = a[ j]
A[ j+1] = t ;
Insertion sort
.۱لیستی با سایز۱ در نظر بگیرید.”اولین عنصر را داخل لیست قرار دهید.“
.۲عمل insertion را تکرار کنید بطوریکه ترتیب داده ها حفظ شود
Insertion sort
Sort 7, 3, 5, 6, 1
Start with 7 and insert 3=> 3,7
Insert 5=>3, 5, 7
Insert 6=>3, 5, 6, 7
Insert 1=>1, 3, 5, 6, 7
Insertion sort
For (i=1 ; i<a.length ; i++)
{// insert a[i] into a[0:i-1]
//code to insert comes here
}
For (i=1 ; i<a.length ; i++)
{// insert a[i] into a[0:i-1]
//code to insert comes here
int t =a[ j]
int j;
For ( j=i-1 ; j>=0 && t <a[ j] ; j–)
A[ j+1] = a[ j]
A[ j+1] = t ;
}
پاورپوینت درمورد ساختمان داده‌ها و الگوریتم
Complexityیا پیچیدگی
پیچیدگی مکانی /حافظه ای
پیچیدگی زمانی
.۱شمارش یک عملگر خاص
.۲شمارش تعداد مراحل
.۳پیچیدگی Asymptotic
Compration count
شمارش مقایسه ای
For (i=1 ; i<a.length ; i++)
{// insert a[i] into a[0:i-1]
//code to insert comes here
int t =a[ j]
int j;
For ( j=i-1 ; j>=0 && t <a[ j] ; j–)
A[ j+1] = a[ j]
A[ j+1] = t ;
}
Compration count
یک نمونه کاراکتری از n را در نظر بگیرید، که در آن n طول لیستی باشد که می خواهیم روی آن
Insertion sort را انجام دهیم.
و تعداد توابع این نمونه کاراکتری را بشمارید.؟؟؟؟
Determine count as a function of this instance characteristic.???
For (j=i-1 ; j>=0 && t <a[ j] ;j–)
A[ j+1] = a[ j];
nچند مقایسه انجام شده است ؟
For (j=i-1 ; j>=0 && t <a[ j] ;j–)
A[ j+1] = a[ j];
شمارش تعداد مقایسات وابسته به a[] وt با توجه به i
Worst-case count=maximum count
Best –case count=minimum count
Avarage count
Worst-case Compration count
For (j=i-1 ; j>=0 && t <a[ j] ;j–)
A[ j+1] = a[ j];
A=[1,2,3,4] and t=0 =>4 compares
A=[1,2,3,..,i] and t=0 =>i compares
for(int i=1; i< n ; i++)
For (j=i-1 ; j>=0 && t <a[ j] ;j–)
A[ j+1] = a[ j];
تعداد کل مقایسات :
Total comprase =1+2+3+…+(n-1)
=(n-1)n/2
Step count
یک مرحله از محاسبات وابسته است به مقادیر n
برای مثال :
۱۰ add , 100 subtracts,1000 multiplies
فقط یک step محسوب میشود .
وبه این مفهوم نمی باشد که با افزایش n یک مرحله نیز به تعداد step اضافه شود.
