دانلود پاورپوینت درس طراحی الگوریتم ها (با شبه کد های c ++) با فرمت ppt ودر249 اسلاید قابل ویرایش
قسمتی از متن پاورپوینت درس طراحی الگوریتم ها (با شبه کد های c ++)
تعداد فصل های پاورپوینت فصل 1 تا 7
فصل اول:
کارایی ، تحلیل و مرتبه الگوریتم ها
این کتاب در باره تکنیک های مربوط به حل مسائل است.
تکنیک ، روش مورد استفاده در حل مسائل است.
مسئله ، پرسشی است که به دنبال پاسخ آن هستیم.
بکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود.
منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.
nنوشتن الگوریتم به زبان فارسی دو ایراد دارد:
1- نوشتن الگوریتم های پیچیده به این شیوه دشوار است.
2- مشخص نیست از توصیف فارسی الگوریتم چگونه
می توان یک برنامه کامپیوتری ایجاد کرد.
الگوریتم 1-1: جست و جوی ترتیبی
Void seqsearch ( int n
constkeytypeS[ ]
keytypex,
index& location)
{
location = 1;
while (location <= n && S[location]! = x)
location++;
if (location>n )
location= 0 ;
3-1 تحلیل الگوریتم ها
nبرای تعیین میزان کارایی یک الگوریتم را باید تحلیل کرد. n
1-3-1 تحلیل پیچیدگی زمانی
nتحلیل پیچیدگی زمانی یک الگوریتم ، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می شود.
T(n) را پیچیدگی زمانی الگوریتم در حالت معمول می گویند.
W(n) را تحلیل پیچیدگی زمانی در بدترین حالت می نامند.
A(n) را پیچیدگی زمانی در حالت میانگین می گویند.
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه)
عمل اصلی: افزودن یک عنصر از آرایه به sum.
اندازه ورودی: n، تعداد عناصر آرایه.
T(n) = n
4-1مرتبه الگوریتم
الگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n
را الگوریتم های زمانی خطی می گویند.
مجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²) ( θ می گویند.
nمجموعه ای ازتوابع پیچیدگی که با توابع درجه سوم محض قابل دسته بندی باشند، n³) ( θ نامیده می شوند.
برخی از گروه های پیچیدگی متداول در زیر داده شده است:
θ(lg n) < θ (n) < θ (n lg n) < θ (n²) < θ (n³) < θ (2 ⁿ)
2-4-1آشنایی بیشتر بامرتبه الگوریتم ها
n
nبرای یک تابع پیچیدگی مفروض ƒ(n) ،O (ƒ (n) ”O بزرگ“
مجموعه ای از توابع پیچیدگی g (n) است که برای آن ها یک ثابت حقیقی مثبت c و یک عدد صحیح غیر منفی N وجود دارد به قسمی که به ازای همه ی N=< n داریم:
g (n) <= c × ƒ (n)
دیدگاه خود را ثبت کنید