بخشی از پاورپوینت
اسلاید 1 :
n
nاین کتاب در باره تکنیک های مربوط به حل مسائل است.
n
nتکنیک ، روش مورد استفاده در حل مسائل است.
n
nمسئله ، پرسشی است که به دنبال پاسخ آن هستیم.
n
n
اسلاید 2 :
nبکار بردن تکنیک منجر به روشی گام به گام (الگوریتم ) در حل یک مسئله می شود.
n
n منظورازسریع بودن یک الگوریتم، یعنی تحلیل آن از لحاظ زمان و حافظه.
اسلاید 3 :
nنوشتن الگوریتم به زبان فارسی دو ایراد دارد:
1- نوشتن الگوریتم های پیچیده به این شیوه دشوار است.
2- مشخص نیست از توصیف فارسی الگوریتم چگونه
می توان یک برنامه کامپیوتری ایجاد کرد.
اسلاید 4 :
3-1 تحلیل الگوریتم ها
nبرای تعیین میزان کارایی یک الگوریتم را باید تحلیل کرد.
n
1-3-1 تحلیل پیچیدگی زمانی
nتحلیل پیچیدگی زمانی یک الگوریتم ، تعیین تعداد دفعاتی است که عمل اصلی به ازای هر مقدار از ورودی انجام می شود.
اسلاید 5 :
nT(n) را پیچیدگی زمانی الگوریتم در حالت معمول می گویند.
nW(n) را تحلیل پیچیدگی زمانی در بدترین حالت
می نامند.
nA(n) را پیچیدگی زمانی در حالت میانگین
می گویند.
n
اسلاید 6 :
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(جمع کردن عناصرآرایه)
عمل اصلی: افزودن یک عنصر از آرایه به sum.
اندازه ورودی: n، تعداد عناصر آرایه.
T(n) = n
اسلاید 7 :
تحلیل پیچیدگی زمانی برای حالت معمول برای الگوریتم(مرتب سازی تعویضی)
n
عمل اصلی: مقایسه S [j] با S[i] .
اندازه ورودی: تعداد عناصری که باید مرتب شوند.
T(n) = n(n -1) /2
اسلاید 8 :
تحلیل پیچیدگی زمانی دربدترین حالت برای الگوریتم(جست و جوی ترتیبی)
عمل اصلی: مقایسه یک عنصر آرایه با x.
اندازه ورودی:, n تعداد عناصر موجود در آرایه.
W (n) = n
اسلاید 9 :
تحلیل پیچیدگی زمانی در بهترین حالت برای الگوریتم(جست وجوی ترتیبی)
n
عمل اصلی: مقایسه یک عنصر آرایه با x.
اندازه ورودی:, n تعداد عناصر آرایه.
B (n) = 1
n
اسلاید 10 :
4-1مرتبه الگوریتم
n
nالگوریتم ها یی با پیچیدگی زمانی ازقبیل n و100n
را الگوریتم های زمانی خطی می گویند.
nمجموعه کامل توابع پیچیدگی را که با توابع درجه دوم محض قابل دسته بندی باشند، n²)(θ می گویند.
n
n
