close
دانلود فیلم
پيچيدگی زمانی

زمان اجرا مقدار زمانی از کامپيوتر است که برنامه برای اجرای کامل مصرف می کند. برای محاسبه پيچيدگی زمان الگوريتم ابتدا تعداد قدم های الگوريتم به صورت تابعی از اندازه مسئله مشخص می شود، برای انجام اين کار تعداد تکرارعمليات اصلی الگوريتم محاسبه می شود و به صورت تابع 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!)

 

محصول مرتبط با این پست : 

بررسی الگوریتم خوشه بندی در ساخت سیستم های توزیع شده

صفحات :۱۵۳

پایان نامه رشته کامپیوتر
  
فیلم های فارسی ساختمان گسستهفیلم های فارسی ساختمان داده هاکتاب عشق شیرین - نسخه کامل
لینک کوتاه پست
  • نکات مهم
    1- لطفا نظر خود را با زبان فارسی بیان کنید
    2- رایتم نظرات اسپم و تبلیغی شما را تایید نمی کند
    3- لطفا نظرات شما بدون ابهام و واضح باشد
  • نام
    ایمیل (منتشر نمی‌شود) (لازم)
    وبسایت
    :):(;):D;)):X:?:P:*=((:O@};-:B/:):S
    نظر خصوصی
    مشخصات شما ذخیره شود ؟[حذف مشخصات] [شکلک ها]
    کد امنیتی
به کانال تلگرام سایت ما بپیوندید