مقدمه‌اي بر
پپيچيدگي الگوريتم‌ها - قسمت اول
مقدمه
امنظور از تحليل پيچيدگي يا كارايي (در اين‌جا منظور «كارايي زماني» است). اين است كه بدانيم از بين دو الگوريتم كه براي حل يك مسأله‌ي خاص طراحي شده‌اند كدام‌يك جواب را سريع‌تر به‌دست خواهد آورد. دليل چنين كاري نسبتاً واضح است چون اصولاً هدف ما از به‌كار گيري كامپيوترها «سرعت در انجام محاسبات» بوده است. بنابراين «تحليل زماني» الگوريتم‌هايي كه براي حل مسائل طراحي مي‌كنيم ما را در «به‌كارگيري بهتر از ماشين محاسبه‌‌گر ياري خواهد كرد.صورت مسأله در تحليل الگوريتم‌ها به‌دست آوردن تابعي برحسب اندازه‌ي ورودي براي اندازه‌گيري زمان اجراي الگوريتم مي‌باشد.
تعريف چند نماد جديد
در طول اين قسمت بد نيست كه صورت مسأله‌ي اصلي را از ياد ببريد! در اين‌جا چند نماد كلي را براساس توابع رياضي تعريف مي كنيم:
يك تابع يك متغيره‌ي به هر عضو مجموعه‌ي A يك عضو از مجموعه‌ي B را متناظر مي‌كند:
توجه كنيد كه هريك از نمادهايي كه در ادامه‌ي اين بخش تعريف مي‌كنيم يك «مجموعه از توابع» را معرف مي‌كنند.
نماد O
گوييم تابع عضو مجموعه‌ي است اگر و تنها اگر ثابت‌هاي مثبت وجود داشته باشند به‌طوري كه به‌ازاي هر داشته باشيم:
به‌طور مثال اگر و باشد در اين صورت:
زيرا اگر قرار دهيم:
در اين صورت به‌ازاي هر داريم:
ادامه دارد ...
براي شركت در مسابقه المپياد به آخرين مسابقه رفته و در قسمت پاسخ جديد ، پاسخ خود را وارد نماييد، همچنين مي توانيد پاسخ خود را از طريق ايميل به آدرس Olympiad@roshd.ir ارسال نماييد. براي ديدن سوال ها، پاسخ ها و اسامي برندگان مسابقات قبلي روي مسابقه كليك كنيد.
مشاوره
|
معرفي كتاب
مصاحبه
زنگ تفريح
آموزش
راهنماي سايت
صفحه اصلي
درباره ما
پرسش و پاسخ علمي
نظرات و پيشنهادات
اخبار
مسابقه