زنگ‌تفریح تصادفی

 پيوندهاي المپياد كامپيوتر
 سايت‌هاي المپياد كامپيوتر
 
 مقدمه‌اي بر پيچدگي الگوريتم‌ها - قسمت آخر!! (زنگ تفريح شماره‌ي 17)
مقدمه‌اي بر پيچدگي الگوريتم‌ها - قسمت آخر!! (زنگ تفريح شماره‌ي 17)زنگ تفريح كامپيوتر
اين هم از آخرين نماد!

نماد

 

اگر براي دو تابع  و  داشته باشيم:
 



و

در اين صورت:
 




در حقيقت مجموعه‌ي  اشتراك دو مجموعه ي  و  مي‌باشد.
اين نماد در حقيقت اصلي‌ترين «نماد پيچيدگي الگوريتم»هاست زيرا در حقيقت مي‌توانيم بگوييم اگر:
 



در اين صورت رشد توابع   به يك اندازه است.
براي درك اين مفهوم به توابع زير توجه كنيد
ياداوري - به ياد داشته باشيد كه خيلي وقت‌ها نماد O به‌جاي  به‌كار مي‌رود!

اگر:




باشد در اين‌صورت:

:



                                         
                              
و اگر:



باشد در اين‌صورت:


:



                                                 

مي‌دانيم كه اگر:
 


باشد در اين‌صورت هر دو رابطه‌ي بالا برقرار است.
حال m را براي ماكزيمم  بگيريد در اين‌صورت داريم‌:


:

مفهوم اين رابطه چيست؟ اين رابطه بيان مي‌دارد كه از جايي به بعد  بين ضرايبي از  قرار دارد. در حقيقت نرخ رشد  مشابه  است.

ادامه ندارد!!

1386/1/17لينک مستقيم

نظر شما پس از تاييد در سايت قرار داده خواهد شد
نام :
پست الکترونيکي :
صفحه شخصي :
نظر:
تاییدانصراف
 زنگ تفريح‌ها

 
 المپياد كامپيوتر

 

     

 

 

صفحه‌ي اصلي

     

 

راهنماي سايت

     

 

 

آموزش

     

 

بانك سوال

     

 

 

مسابقه

     

 

 

زنگ تفريح

     

 

 

مصاحبه و گزارش

     

 

 

معرفي كتاب

     

 

 

مشاوره

     

 

 

پرسش‌و‌پاسخ‌علمي

     

 

اخبار

 

فعاليت‌هاي علمي

 بازديدها
كاربران غيرعضو آنلاينكاربران غيرعضو آنلاين:  8144
 كاربران عضو آنلاين:  0
  کل كاربران آنلاين:  8144