سیده آمین ارمان
کاربر نگاه دانلود
باتوجه به نزدیکی بسیار زیاد مطالب این مبحث با و توصیه می‌شود ابتدا مطالب مربوط به آنها
مطالعه شود و سپس برای مطالعهٔ دقیق تر موضوع ادامهٔ این مبحث را مطالعه نمایید.
ارزیابی کارائی
الگوریتم‌های مختلفی برای حل یک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترین الگوریتم باید معیاری جهت مقایسه کارائی
الگوریتم‌ها داشته باشیم.
ارزیابی در دو مرحله انجام می‌شود:
بعد از پیاده سازی الگوریـتم با یک ، آمار حقیقی درباره زمان و حافظه مصرف شده توسط الگوریتم در حین اجرا جمع
آوری می‌شود.
پیچیدگی زمانی
زمان اجرای یک برنامه به موارد زیر بستگی دارد
منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه نمی‌باشد بلکه منظور واحدهای منطقی است که رابـ ـطه بین بزرگی (n) یک فایل یا یک آرایه و زمان مورد نیاز برای پردازش داده‌ها را شرح می‌دهد.(توجه کنید که هر دستور یک واحد زمانی اشغال می‌کند.)
مثلاً دستورات ;a=b و;c/d-e*; a=b هر کدام یک واحد زمانی را دربردارند.
مجموع تعداد عملکردهای اجرایی، زمان اجرای برنامه را می‌رساند و مستقل از ماشین است.
یک گام یا مرحله برنامه، یک قسمت یا بخش با معنی برنامه‌است (از لحاظ مفهومی یا نحوی) که زمان اجرای آن مستقل از مشخصات نمونه‌است.
بعنوان مثال تمام عبارت زیر یک مرحله‌است.
return (a+b-c) / (a+b)+۴٫۰ ;
بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به ;نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی
بدون فراخوانی برابر یک می‌باشد. و در دستورات غیربازگشتی حلقه for، while، repeat until به تعداد تکرار حلقه در نظر گرفته می‌شود.
هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست
آوردن این تابع رشد است.
برای مثال هرچه زبان برنامه نویسی() به نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید
زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.
برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم‌های الگوریتم به صورت تابعی از اندازه مسئله مشخص می‌شود، برای انجام این کار
تعداد تکرارعملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه
ورودی به اندازه کافی بزرگ است نشان می‌دهد، بدست می‌آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی‌های
مختلف
با استفاده از نمادها O، Θ وΩ که در بخش بعدی با آنها آشنا می‌شویم، بیان می‌شود. این متن اصلی مقاله‌است که از کتاب خاصی و کتاب دیگری و یک پانویس هم دارد *
زمان اجرای الگوریتم
زمان اجرای یک الگوریتم از مسائل مهم طراحی الگوریتم می‌باشد و غالبا کارایی الگوریتم‌ها را از روی زمان اجرای آنها بررسی می‌شود. همان طور که می دانیم الگوریتم عبارتست از: مجموعه‌ای از دستورات و دستورالعمل‌ها برای حل مسئله که شرایط زیر را باید دارا باشد:
عوامل دخیل در زمان اجرای برنامه:
برای محاسبه تابع (T(n برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم:
مثال: تعداد کل مراحل برنامه زیر را محاسبه کنید.
0 (int func(int n
۰ }
0 ;int i
1 ;int sum=۰
FOR(i=1;i<=n;i++) n+1
sum=sum+i; n
1 ;return sum
۰ {
کل عبارت مساوی ۲n+3 می‌شود. همان طور که مشاهده می‌کنید زمان اجرای هر عبارت جایگزینی یا محاسباتی را مساوی ۱ واحد زمانی فرض می‌کنیم. هم چنین دستور داخل حلقه n بار انجام می‌شود ولی آزمایش کردن شرط حلقه در خط for به تعداد n+1 بار صورت می‌گیرد. دستور Return نیز مساوی یک واحد زمانی است.
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
(++For(i=1 ; i<=m ;i
(++For(j=1 ; j<=n ; j
; A=a+1
T(N)=MN
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
(++For(j=1 ; j<=n ; j
++For(i=1 ; i<=j ;i
;A=a+1
تعداد اجرا شدن A=a+1; I J
۱ بار ۱ ۱
۲ بار ۱٬۲ ۲
۳بار ۱٬۲٬۳ ۳
- - -
- - -
- - -
n بار 1,2,3,... ,n n
تعداد اجرا شدن دستور اصلی= 3,2,1,... ,n(n+1)/2 = n
T(n)=n(n+1)/2
== پیچیدگی حافظهخطای یادکرد: خطای یادکرد: برچسب تمام کنندهٔ </ref> بدون برچسب <ref> کتاب به وضوح توضیح داده شده‌است.
برای آنکه مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.
تحلیل پیچیدگی زمانی:
هنگامی که کارایی الگوریتم‌ها را بر حسب زمان تحلیل می‌کنیم، تعداد چرخه‌های واقعی CPU را تعیین نمی‌کنیم، زیرا این به کامپیوتر خاصی که الگوریتم روی آن اجرا می‌شود بستگی دارد. در عوض به معیاری نیاز داریم که مستقل از کامپیوتر، زبان برنامه نویسی، برنامه نویس و خلاصه همه جزئیات الگوریتم از قبیل افزایش اندیس حلقه‌ها و غیره باشد. به طور کلی تحلیل پیچیدگی زمانی یک الگوریتم عبارت است از تعیین تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود.
به کار بستن نظریه:
هنگام به کار بستن نظریه تحلیل الگوریتم‌ها، گاهی باید از زمان لازم برای اجرای عمل اصلی دستورات سربار و دستورات کنترلی روی کامپیوتری که الگوریتم را اجرا می‌کند آگاه باشیم. منظور از دستورات سربار دستوراتی نظیر مقدار دهی اولیه پیش از شروع حلقه هاست. تعداد دفعاتی که این دستورات اجرا می‌شوند با تعداد ورودی افزایش نمی‌یابد.
تحلیل درستی الگوریتم:
به معنای تحلیل کارایی بر حسب زمان یا حافظه است.
مطالعه شود و سپس برای مطالعهٔ دقیق تر موضوع ادامهٔ این مبحث را مطالعه نمایید.
ارزیابی کارائی
الگوریتم‌های مختلفی برای حل یک مسئله ممکن است طراحی شده باشند. برای انتخاب بهترین الگوریتم باید معیاری جهت مقایسه کارائی
الگوریتم‌ها داشته باشیم.
ارزیابی در دو مرحله انجام می‌شود:
- آنالیز کارائی
- اندازه گیری کارائی
- پیچیدگی زمانی time complexity
- پیچیدگی حافظه space complexity
بعد از پیاده سازی الگوریـتم با یک ، آمار حقیقی درباره زمان و حافظه مصرف شده توسط الگوریتم در حین اجرا جمع
آوری می‌شود.
پیچیدگی زمانی
زمان اجرای یک برنامه به موارد زیر بستگی دارد
- سخت‌افزار
- سیستم‌عامل
- کمپایلر
- نوع الگوریتم
- آرایش داده‌های ورودی
منظور از واحد زمانی، واحدهای زمانی واقعی مانند میکرو یا نانو ثانیه نمی‌باشد بلکه منظور واحدهای منطقی است که رابـ ـطه بین بزرگی (n) یک فایل یا یک آرایه و زمان مورد نیاز برای پردازش داده‌ها را شرح می‌دهد.(توجه کنید که هر دستور یک واحد زمانی اشغال می‌کند.)
مثلاً دستورات ;a=b و;c/d-e*; a=b هر کدام یک واحد زمانی را دربردارند.
مجموع تعداد عملکردهای اجرایی، زمان اجرای برنامه را می‌رساند و مستقل از ماشین است.
یک گام یا مرحله برنامه، یک قسمت یا بخش با معنی برنامه‌است (از لحاظ مفهومی یا نحوی) که زمان اجرای آن مستقل از مشخصات نمونه‌است.
بعنوان مثال تمام عبارت زیر یک مرحله‌است.
return (a+b-c) / (a+b)+۴٫۰ ;
بنابراین تعداد مراحل برای هر عبارت یک برنامه بستگی به ;نوع عبارت دارد، بطوریکه در عبارات توضیحی برابر صفر و در دستور انتسابی
بدون فراخوانی برابر یک می‌باشد. و در دستورات غیربازگشتی حلقه for، while، repeat until به تعداد تکرار حلقه در نظر گرفته می‌شود.
هدف از محاسبه پیچیدگی زمانی یک الگوریتم این است که بفهمیم نیازمندی یک الگوریتم به زمان با چه تابعی رشد می‌کند و هدف اصلی بدست
آوردن این تابع رشد است.
برای مثال هرچه زبان برنامه نویسی() به نزدیک تر باشد، برنامه با سرعت بیشتری به جواب خواهد رسید
زمان اجرا مقدار زمانی از کامپیوتر است که برنامه برای اجرای کامل مصرف می‌کند.
برای محاسبه پیچیدگی زمان الگوریتم ابتدا تعداد قدم‌های الگوریتم به صورت تابعی از اندازه مسئله مشخص می‌شود، برای انجام این کار
تعداد تکرارعملیات اصلی الگوریتم محاسبه می‌شود و به صورت تابع f بیان می‌شود. سپس تابع g، که مرتبه بزرگی تابع f را وقتی اندازه
ورودی به اندازه کافی بزرگ است نشان می‌دهد، بدست می‌آید. در نهایت پیچیدگی الگوریتم برای نشان دادن رفتار الگوریتم با ورودی‌های
مختلف
با استفاده از نمادها O، Θ وΩ که در بخش بعدی با آنها آشنا می‌شویم، بیان می‌شود. این متن اصلی مقاله‌است که از کتاب خاصی و کتاب دیگری و یک پانویس هم دارد *
زمان اجرای الگوریتم
زمان اجرای یک الگوریتم از مسائل مهم طراحی الگوریتم می‌باشد و غالبا کارایی الگوریتم‌ها را از روی زمان اجرای آنها بررسی می‌شود. همان طور که می دانیم الگوریتم عبارتست از: مجموعه‌ای از دستورات و دستورالعمل‌ها برای حل مسئله که شرایط زیر را باید دارا باشد:
- دقیق باشد
- مراحل ان به ترتیب اجرا شود
- پایان پذیر باشد
عوامل دخیل در زمان اجرای برنامه:
- سرعت سخت افزار
- نوع کامپایلر
- اندازه داده ورودی
- ترکیب داده‌های ورودی
- پیچیدگی زمانی الگوریتم
- پارامترهای دیگر که تاثیر ثابت در زمان اجرا دارند.
برای محاسبه تابع (T(n برای یک الگوریتم موارد زیر را باید در محاسبات در نظر بگیریم:
- زمان مربوط به اعمال جایگزینی که مقدار ثابت دارند.
- زمان مربوط به انجام اعمال محاسباتی که مقدار ثابت دارند.
- زمان مربوط به تکرار تعدادی دستور یا دستورالعمل
- زمان مربوط به توابع بازگشتی
مثال: تعداد کل مراحل برنامه زیر را محاسبه کنید.
0 (int func(int n
۰ }
0 ;int i
1 ;int sum=۰
FOR(i=1;i<=n;i++) n+1
sum=sum+i; n
1 ;return sum
۰ {
کل عبارت مساوی ۲n+3 می‌شود. همان طور که مشاهده می‌کنید زمان اجرای هر عبارت جایگزینی یا محاسباتی را مساوی ۱ واحد زمانی فرض می‌کنیم. هم چنین دستور داخل حلقه n بار انجام می‌شود ولی آزمایش کردن شرط حلقه در خط for به تعداد n+1 بار صورت می‌گیرد. دستور Return نیز مساوی یک واحد زمانی است.
- ;نکته
- ;نکته
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
(++For(i=1 ; i<=m ;i
(++For(j=1 ; j<=n ; j
; A=a+1
- ;نکته
T(N)=MN
مثال: دستور اصلی a=a+1 در قطعه برنامه زیر چند بار اجرا می‌گردد؟
(++For(j=1 ; j<=n ; j
++For(i=1 ; i<=j ;i
;A=a+1
- ;نکته
تعداد اجرا شدن A=a+1; I J
۱ بار ۱ ۱
۲ بار ۱٬۲ ۲
۳بار ۱٬۲٬۳ ۳
- - -
- - -
- - -
n بار 1,2,3,... ,n n
تعداد اجرا شدن دستور اصلی= 3,2,1,... ,n(n+1)/2 = n
T(n)=n(n+1)/2
== پیچیدگی حافظهخطای یادکرد: خطای یادکرد: برچسب تمام کنندهٔ </ref> بدون برچسب <ref> کتاب به وضوح توضیح داده شده‌است.
برای آنکه مشخص کنیم میزان کارایی یک الگوریتم در حل یک مسئله تا چه حد است باید به تحلیل آن بپردازیم.
تحلیل پیچیدگی زمانی:
هنگامی که کارایی الگوریتم‌ها را بر حسب زمان تحلیل می‌کنیم، تعداد چرخه‌های واقعی CPU را تعیین نمی‌کنیم، زیرا این به کامپیوتر خاصی که الگوریتم روی آن اجرا می‌شود بستگی دارد. در عوض به معیاری نیاز داریم که مستقل از کامپیوتر، زبان برنامه نویسی، برنامه نویس و خلاصه همه جزئیات الگوریتم از قبیل افزایش اندیس حلقه‌ها و غیره باشد. به طور کلی تحلیل پیچیدگی زمانی یک الگوریتم عبارت است از تعیین تعداد دفعاتی که عمل اصلی به ازای هر مقدار از اندازه ورودی انجام می‌شود.
به کار بستن نظریه:
هنگام به کار بستن نظریه تحلیل الگوریتم‌ها، گاهی باید از زمان لازم برای اجرای عمل اصلی دستورات سربار و دستورات کنترلی روی کامپیوتری که الگوریتم را اجرا می‌کند آگاه باشیم. منظور از دستورات سربار دستوراتی نظیر مقدار دهی اولیه پیش از شروع حلقه هاست. تعداد دفعاتی که این دستورات اجرا می‌شوند با تعداد ورودی افزایش نمی‌یابد.
تحلیل درستی الگوریتم:
به معنای تحلیل کارایی بر حسب زمان یا حافظه است.
