زمان اجرا مقدار زمانی از کامپيوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پيچيدگی زمان الگوريتم ابتدا تعداد قدم های الگوريتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام اين کار تعداد تکرارعمليات اصلی الگوريتم محاسبه می شود و به صورت تابع f(n) (که n تعداد ورودی هاست) بيان می شود. سپس تابع g(n)، که مرتبه بزرگی تابع f(n) را وقتی اندازه ورودی به اندازه کافی بزرگ است نشان می دهد، بدست می آيد. در نهايت پيچيدگی الگوريتم برای نشان دادن رفتار الگوريتم با ورودی های مختلف با استفاده از نمادها O ، Θ و Ω بيان می شود.
تعريف Big-O (حدبالا)
تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيمf(n) = O(g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≤ cg(n) برقرار باشد.
اين نماد حدبالائی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بدترين حالت و بيشترين زمان اجرا را برای مقادير معين ورودی دارد
تعريف Big-Ω (حدپائين)
تابع f(n) را نظر بگيريد که برای کليه n≥0 است ، می گوئيم f(n) = Ω (g(n)) اگر ثابت های مثبت n0 و c وجود داشته باشند به طوريکه از يک n0 به بعد هميشه f(n)≥ cg(n) برقرار باشد.
اين نماد حد پائينی برای تابع f(n) می دهد و وقتی بکار می رود که رفتار الگوريتم بهترين حالت و کمترين زمان اجرا را برای مقادير معين ورودی دارد
تعريف Big-Θ (حدمتوسط)
تابع f(n) را نظر بگيريد که برای کليه n≥0 است، می گوئيم f(n) = Θ(g(n)) اگر ثابت های مثبت n0، c1 و c2 وجود داشته باشند به طوريکه از يک n0 به بعد هميشه c1g(n) ≤f(n) ≤ c2g(n) برقرار باشد.
اين نماد حدمتوسطی برای تابع f(n) می دهد و زمان اجرای الگوريتم را به صورت ميانگينی از تعداد عمليات انجام شده با کليه نمونه ورودی های مسئله نشان می دهد.
قضيه. اگر f(n)=amnm+am-1nm-1+…+a1n+a0 در اينصورت f(n)=O(nm) است.
مثال. الگوريتم مرتب سازی حبابی را درنظر بگيريد.
for (i:=1 to n-1)
for (j:=1 to n-1)
if aj>aj+1 then exchange(aj,aj+1)
با درنظر گرفتن عمل مقايسه بعنوان عملگر اصلی، دستور If در الگوريتم فوق (n-1)2 بار تکرار می شود. بنابراين f(n)= (n-1)2=n2-2n+1 و طبق قضيه g(n)=n2 است. بنابراين پيچيدگی الگوريتم فوق برابر با O(n2) می باشد.
نکته. اگر زمان الگوريتم وابسته به ورودی نباشد با نماد O(1) نشان داده می شود.
نکته. بايد به اندازه کافی الگوريتم را درک کرده باشيم تا بهترين و بدترين رفتار را توليد و محاسبه کنيم. چون برآورد رفتار آماری ورودی ها امری دشوار است، در اکثر موارد به بدترين حالت قناعت می کنيم.
نکته. اگر الگوريتم شامل بخش های مختلفی باشد که هر قسمت پيچيدگی متفاوتی دارد، مرتبه بزرگی هر قسمت را پيدا کرده و بزرگترين مرتبه را بعنوان پيچيدگی کل الگوريتم درنظرمی گيريم.
غالبا پيچيدگی g(n) يکی از توابع زير است: n (پيچيدگی خطی)، log n (لگاريتمی)، na (چندجمله ای) و an که a≥2 (نمائی).
در زير مرتبه اجرائی چند تابع به ترتيب صعودی نوشته شده است.
O(1) < O(log n) < O(n) < O(n log n) < O(n2) < O( n3) < O(2n) < O(n!)
محصول مرتبط با این پست :
عنوان : 
تعداد صفحات :
نوع فایل
حجم فایل :
دانلود نمونه سوالات واقعی آزمون MSRT - با پاسخ نامه 
دانلود كتاب محاسبات عددي(دكتر نيكوكار و دكتر درويشي)
دانلود جزوات رشته مهندسی کامپیوتر و IT
دانلود کتابهای دانشگاهی رشته مهندسی مکانیک
مجموعه آموزشی درس ریاضی مهندسی 
دانلود فیلم های مدار منطقی دانشگاه شریف - محمود تابنده
دانلود فیلم های معماری کامپیوتر دانشگاه شریف - مازیار گودرزی
دانلود جزوه ریاضی مهندسی – استاد حسنی
دانلود جزوه ریاضی ۲ دانشگاه امیر کبیر-دکتر عربزاده
دانلود جزوه ریاضی عمومی ۲ -میثم برزگر