پاورپوینت پيچيدگي زماني الگوريتم (pptx) 15 اسلاید
دسته بندی : پاورپوینت
نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )
تعداد اسلاید: 15 اسلاید
قسمتی از متن PowerPoint (.pptx) :
بنام خدا
پيچيدگي زماني الگوريتم زير کدام است؟
sum = 0;
for ( i = 0; i < n; i++ )
for ( j = 0; j < i; j++ )
for ( k = 0; k < 3; k++ )
sum++;
O(n3)
O(n)
O(nlogn)
O(n2)
تعداد دفعات تکرار دستور خط 3 چندتاست؟
for ( k = 0; k <= n – 1; k++ )
for ( i = 1; i <= n – k; i++ )
a[i][i+k] = k;
1) 2)
3) 4)
تابع زير براي محاسبه بزرگترين مقسوم عليه دو عدد نوشته شده است.
int gcd(int a, int b)
{
if ( b == 0 )
return a;
else
return gcd(b, a mod b);
}
در اين صورت مي توان گفت مرتبه زماني الگوريتم ........ است.
1) 2)
3) 4)
يک آرايه از اعداد صحيح بصورت A[1..m] مفروض است، به طوريکه
در اين صورت مرتبه اجراي الگوريتم زير کدام يک از گزينه هاي زير است؟
T := 0;
For i := 1 to m do
for j := 1 to A[i] do
T := T + 1;
1) 2)
3) 4)
فرض کنيد زمان اجراي الگوريتمي روي n ورودي، T(n) بوده که بصورت زير تعريف مي شود:
زمان اجراي الگوريتم مزبور برابر کدام گزينه است؟
O(n)
O(nlogn)
O(n3/2)
O(n2)
تابع بازگشتي زير را در نظر بگيريد:
int test(int n)
{
if ( n <= 2 )
return 1;
else
return test(n-2) + test(n-2);
}
زمان اجراي تابع فوق برابر است با:
1) 2)
3) 4)
روابط بازگشتي زير را حل کنيد:
The Master Method (from CLRS)