سوال درس ساختمان داده

[engeneer_19]

F(n) € Ώ (g(n)) اگر داشته باشيم كدام گزينه صحيح است؟

1. f(n) € o (g(n))

2. g(n) € o(f(n))

3. f(n) € θ (g(n))

4. g(n) € θ (f(n))

الگريتمي به صورت زير براي ضرب دو عدد x , y ارايه شده.هزينه اين الگريتم كدام است؟

Int product (unsigned int x,unsigned int y)
{
If(y==1) return (x)
Return (x+product (x,y-1));
}

گزينه ها:

O(x)
O(y)
O(xy)
O(x+y)

[آبجی]

اول یه توضیح کلی میدم بعد جواب سوالات رو میدم چون گفتی کامل بگم :

چون تاپیکها مثل هم بود یکی شو حذف کردم .

برای محاسبه زمان اجرای یک برنامه باید نکات زیر رو رعایت کنی :

1- عبارات ساده محاسباتی دارای پیچیدگی زمانی 1 هستند مثل :
a+b , a*b , ++a, a=b , a= b +c, .....

2- تعریف متغییرها فاقد پیچیدگی زمانی هست مثل :
int a
int add(int, int).

3- {} فاقد یپچیدگی زمانی هست .

4- دستور return دارای پیچیدگی زمانی یک هست .

5- دستور for برای n بار تکرار دارای پیچیدگی زمانی

6- پیچیدگی بدنه حلقه برابر با پیچیدگی بدنه ضربدر تعداد تکرار اون

خب فکر کنم با این توضیحات حالا پیدا کردن پیچیدگی زمانی برات اسون شده باشه .

فکر میکنم همین شش مورد بود و چیز دیگهای نبود .

[آبجی]

الگريتمي به صورت زير براي ضرب دو عدد x , y ارايه شده.هزينه اين الگريتم كدام است؟

Int product (unsigned int x,unsigned int y)
{
If(y==1) return (x)
Return (x+product (x,y-1));
}

گزينه ها:

O(x)
O(y)
O(xy)
O(x+y)

خب برای حل این برات یه مثال میزنم :


عددها رو اینطور فرض میکنیم :
5 = x
y =3

که در مرحله اول میشه

(3و5)
}

if (3==1)return 5:
return (5+(product(5,2):
{

مرحله دوم :

(2و5)
}
if (2==1)return 5:
return (5+(product(5,1):
{

مرحله سوم :

(1و 5)
}
if (1==1)return 5:
که همینجا متوقف میشه
{

که مقدار 5 رو به ما میدهد که همون x مونه .
این محاسبه ضرب اعداد طبیعی هست که حالت توفق اون هم y==1 هست .

موفق باشی .

[آبجی]

F(n) € Ώ (g(n)) اگر داشته باشيم كدام گزينه صحيح است؟

1. f(n) € o (g(n))

2. g(n) € o(f(n))

3. f(n) € θ (g(n))

4. g(n) € θ (f(n))

خب حالا جواب این سوالت :

اول یه سری برات توضیح میدم :
BIG -OH
با علامت O نشان داده میشود پیچیدگی زمانی یا مرتبه اجرایی الگوریتم رو نشون میده . یعنی بزرگترین درجه بدون ضریب - کوچکترین کران بالا
BIG - OMEGA
بزرگنرین کران پایین که با علامت Ώ نشون میدن .
On کران بالا پس باید از T n بزرگتر از باشد .
Ώ nیعنی کران پایین یعنی زمانی که Ώ nمیدهد باید ازTn کوچکتر باشه .
نماد تتا اگرΏ n به توان دو وΏ n این به توان چهار باشهΏ n به توان سه میباشد .
پس در کل :
F(n) € Ώ (g(n))
یعنی
g(n)<=f(n) هست .

[بانوثریا]

توضیح کامل این موارد در کتاب طراحی الگوریتم(پیام نور) وجود داره که کامل توضیح داده شده