ورود / ثبت نام
در این آموزش با روشهای تحلیل الگوریتم آشنا می‌شوید و در قالب مثالهای مختلف مفاهیم مربوط به مرتبه زمانی را یاد خواهید گرفت. بعد از مشاهده ویدیو تمرین های متنوعی از مفاهیم این جلسه ارائه شده است که می‌توانید آموخته های خود را محک بزنید.
تمرین و نکات تکمیلی جلسه دوم درس ساختمان داده
در ویدیوی آموزشی بالا به تحلیل 15 الگوریتم پرداخته شد. در ادامه چند الگوریتم جدید به عنوان تمرین ارائه می‌شود:
1- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
x++;
n--;
}
توجه داشته باشید که در خط 5 دستور –n نوشته شده است.
2- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i++) for(j=1;j<=n;j++) x++; n--;
3- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i++){
for(j=1;j<=n;j++)
x++;
j=1;
while(j<n){
x++;
j=j*2
}
}
4- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i++) for(j=1;j<=3*i;j++) for(k=1;k<=3*n;k++) cout<<"*";
راهنمایی: از ایده مثال سوم (روش دوم) و مثال چهارم که در ویدیو توضیح داده شده است استفاده کنید.
5- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i=i*2) for(j=1 ; j<=n; j++) cout<< "*";
6- مرتبه زمانی شبه کد زیر را محاسبه کنید:
for(i=1;i<=n;i=i*2) for(j=1;j<=n;j=j*2) for(k=1;k<=j;k++) cout<<"*";
7- مرتبه زمانی شبه کد زیر را محاسبه کنید:
i=2;
while(i<=n){
cout<<i;
i = i*i;
}
جلسه سوم نداره دوره؟
سلام، جلسه سوم مربوط به ماتریس اسپارسه که متاسفانه سر کلاس ضبط نشده بود و فرصت نکردم دوباره ضبط کنم
سلام
خیلی ممنون برای این دوره. واقعا عالیه
کاش یه وقتی برای قسمت ۳ بذارید و مجددا ضبط کنید. دوره خیلی خوبیه و واقعا حیفه ناقص باشه
ممنون از نظرت، چشم حتما تو برنامه میذارم
سلام استاد خسته نباشید ، واقعا حیف نیست جلسه سوم این آموزش رو نمیزارید ، ممنون میشم اگه این کار رو انجام بدین
سلام، ممنون از لطفت. خیلی از دوستان هم در یوتیوب و هم در سایت به من پیام دادن که این جلسه رو کامل کنم و من هم فعلا شرمنده همه دوستان هستم که فرصت نکردم این جلسه رو دوباره ضبط کنم. مشکل اصلی هم سر اینه که فایلهای پاورپوینتش رو ندارم و درست کردن پاورپوینتش زمان میبره. تمام سعیم رو میکنم قبل از امتحانات پایانترمتون آماده کنم که اگه برای دانشگاه نیاز دارید بتونید استفاده کنید.
سلام استاد خسته نباشید خیلی ممنونم برای این دوره فوق العاده. میشه بگین چه مباحثی رو توی جلسه سوم توضیح داده بودین به جز ماتریس ها؟
سلام، خوشحالم که این آموزشها براتون مفید بوده. تو جلسه سوم در مورد ماتریس اسپارس و الگوریتمهای اون صحبت شده. استراکچر ماتریس اسپارس، جمع دو ماتریس اسپارس، و ترانهاده ماتریس اسپارس…
که برای ترانهاده دو الگوریتم میگیم، یکیش مرتبه زمانیش m*n هست و الگوریتم دوم اگر اشتباه نکنم m+n
سلام وقت بخیر من نمیدونم چرا این پیچیدگی رو درست متوجه نمیشم واقعا الان آخر فیلم سه تا مثال زده بودین مثال دوم چرا تتاش شد Nlog2n چون داشت در دو ضرب میشد؟ میشه یه راهنمایی کنید که ما چه وقت بفهمیم باید از لوگ استفاده کنیم؟ وقتی که اعداد به سمت n میل میکنند؟ ممنون میشم جواب بدید
سلام، برا سوالی که پرسیدی بیا فرض رو بر این بذار که حلقه for مربوط به i رو نداریم (حذفش کن)
حالا حلقه فور j رو در نظر بگیر. اگه j یکی یکی میرفت جلو خب مرتبه زمانی میشه n ولی الان تو اندیسمون داره هی ضرب در 2 میشه. یعنی اول 1 بعدش میشه 2 بعدش میشه 4 بعدش میشه 8…
برای همین میشه logn در مرتبه 2. (اینو تو مثال های قبلی حل توضیح دادم)
حالا چون تو حلقه j ما یه فور k داریم که یکی یکی میره جلو پس میشه n و کل کدمون میشه n logn
همه صحبتایی که کردم با این فرض بود که حلقه i رو حذف کنیم. اگه این دستور داخل فور i قرار بگیره با توجه به توضیحاتی که برای j دادم باید به راحتی تشخیص بدی که حلقه i مرتبه زمانیش logn میشه و این یعنی دستورات داخل فور i داره logn بار تکرار میشه. پس مرتبه کلیش میشه:
n * logn * logn
(دقت کن عدد 2 در ویدیو به معنی توان دوم است نه ضرب در 2)
کاش جواب تمرین هارو هم میذاشتید 🙁
تمرین ها رو در یوتیوبم جواب دادم. بگردید پیداش میکنید ولی سعی میکنم تا آخر دی ماه جوابها رو در سایت هم بذارم
youtube.com/jahangirics
عالی توضیح دادید خیلیییی ممنونم ازتون که جوابمو دادید کاملا متوجه شدم بله فهمیدم اشتباهم کجا بود استاد شما طراحی الگوریتم هم تدریس میکنید؟ من دو ماه دیگ ارشد دارم میخوام حداقل این دو تا درس که به هم مربوطه رو طوری بخونم که بتونم تست بزنم با آموزش شما هم فقط فهمیدم این درس رو با اینک کلی آموزش دیگ حتی خریداری کردم هیچکدوم اینطوری توضیح ندادند
خواهش میکنم.
آموزش به صورت آماده و ویدیویی به این شکلی که برای ساختمان داده دیدید خیر، ندارم.
ولی اگه تمایل به برگزاری کلاس خصوصی داشته باشید به تعداد جلسات محدود و کم میتونیم داشته باشیم. اگه تمایل دارید به من ایمیل بزنید: jahangirics@gmail.com
وقتتون بخیر استاد میشه ازتون یه سوال راجب این قسمت بپرسم
هزینه اجرای این قطعه کد چجوری بدست میاد؟
T(n)={1 n =1
n+f(n−1) n > 2
من تو بدست اوردن اینا قاطی میکنم نمیتونمم بیخیالش بشم چون تو ارشد حتما هست 🙁
سلام، فکر کنم تو خط دوم اشتباه نوشتید و به جای f(n-1) باید T(n-1) بذارید. اگه چیزی که شما نوشتید درسته پس باید بدونیم تابع f چیه
اما اگر چیزی که من میگم باشه یعنی میشه این:
T(n) = n + T(n-1)
یکی از روشهای ساده برای حل معادلات بازگشتی روش جای گذاریه. یعنی شما باید جای T(n-1) معادلش رو بذاری. T(n-1) رو شما خیلی راحت از معادله بالا میتونی بدست بیاری:
T(n-1) = n-1 + T(n-2)
(اگه متوجه نشدی چرا اینجوری شد کافیه توی معادله اول به جای n بیای n-1 بذاری.
پس با توجه به معادله دوم میتونی معادله اول رو اینجوری بنویسی:
T(n)= n + T(n-1) = n + (n-1 + T(n-2))
اگر این معادله رو به همین شمل ادامه بدی میبینی که T(n) برابر میشه با:
T(n) = n + n-1 + n-2 + n-3 … + 1
که همون مجموع 1 تا n میشه و مرتبه زمانی برابر n به توان 2
سپاس از وقتی که میذارید و پاسخ میدید خیلی ممنونم وقتی حل میشه و به جواب میرسم تازه میفهمم چقدر راحت بود….!!!!
آره، همون ضرب المثل معما چو حل گشت …
😁