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