همونطور که میدونیم ، ممکنه الگوریتم های مختلفی برای حل یک مسئله وجود داشته باشن . مثلا برای مرتب سازی یک سری داده ، الگوریتم هایی نظیر : Bubble sort-Selection sort و .....وجود دارن . برای تشخیص دامنه ی کارآمدی الگوریتم ها ، به معیار هایی نظیر پیچیدگی زمانی و پیچیدگی فضای حافظه نیاز داریم. بنابراین منظور
ما از تجزیه و تحلیل الگوریتم ها ، مشخص کردن زمان اجرای برنامه ها هست . هر پردازنده در هرلحظه بیش از یک دستور رو نمیتونه اجرا کنه و این مستقل از نوع پردازنده و سیستم هست. پس هر برنامه در کامپیوتر ها باید دستور به دستور انجام بشه و بنابراین تعداد دستورات برنامه ، مدت زمان اجرای برنامه را نشون میدن . هدف از
تعیین تعداد مراحل این است که بتونیم پیچیدگی زمانی دو برنامه روکه عمل مشابهی انجام می دن مقایسه کنیم و بتونیم میزان افزایش زمان اجرا رو در زمان تغییر مشخصات نمونه ، پیشبینی کنیم . الان ، اصطلاحات و نمادهایی رو معرفی می کنیم که ما رو قادر می سازه عبارات با معنی در مورد زمان و فضای پیچیدگی یک برنامه ایجاد کنیم .

معمولا زمان اجرای یک برنامه رو با Tn نشون میدن .
اما یکی از نماد های مهم نماد اوی بزرگ هست .

تعریف big O: حد بالای زمان اجرای برنامه هست . به معنای دیگر ، زمان اجرای یک برنامه در بدترین حالت . فرض کنیم fn زمان اجرای برنامه بر حسب n باشه. میگیم الگوریتم دارای زمان اجرای Ogn هست اگه c>0 وجود داشته باشه به طوریکه
fn<=cgn

وقتی میگیم On^2 یعنی تمام توابعی که رشدشون کمتر یا مساوی تابع n^2 هست . و وقتی پیچیدگی زمانی یک الگوریتم On^2 باشه یعنی در بدترین حالت ممکن ، تابع پیچیدگی زمانیش از n^2 بیشتر نمیشه ..پس پیچیدگی رو برحسب یک تابع بیان میکنیم .

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

O(log n) < O(n) < O(nlog n) < O(n2) < O(n3) < O(n!)

پس مثلا الگوریتمی که مرتبه ی زمانیش در بدترین حالت ممکن برابر با log n باشه ، بسیار از لحاظ زمانی بهتر از الگوریتمی با زمان اجرای n^3 خواهد بود .

تعریف Ω
حد پایین زمان اجرای یک برنامه هست . یعنی زمان اجرای یک برنامه در بهترین حالت. میگیم الگوریتم دارای زمان اجرای Ωgn هست اگه
fn≥Ωgn

پس Ωgn شامل توابعی هست که رشدشون بزرگتر یا مساوی gn باشه. الگوریتمی با چنین مرتبه ای هم در بهترین حالت دارای پیچیدگی زمانی gn میشه

دوستان عزیز ..
سوال مسابقه ی شماره ی 4 رو تقدیم می کنیم که از مبحث ساختمان داده ها هست . لطف کنید جواب درست رو به @SaeedZiadid بفرستید .

کتابی رو در بالا براتون قرار دادیم به نام "منطق در علوم کامپیوتر".☝️☝️☝️☝️☝️
این کتاب برای کسانی که درس منطق و نظریه ی مجموعه ها رو دارند ، توصیه میشه .. البته هر دانشجوی علوم ریاضی بهتر هست که چنین مطالبی رو فرا بگیره

انشاءالله امروز بعد از ظهر با قسمت بعدی عیدانه در خدمت شما خواهیم بود🌹🌹

🎄🌲🌳🌿🌱🌴☘🍀🌺🌹🌷🌸🌼💐

پایان قسمت هفتم عیدانه ی علوم کامپیوتری

با سلام خدمت همه ی شما دوستان عزیز .. با هشتمین قسمت از عیدانه ی علوم کامپیوتری در خدمت شما هستیم .. با ما همراه باشید🌹🌹

سوال مسابقه رو با هم میبینیم یک بار دیگه

لطف کنید جواب درست رو به @SaeedZiadid بفرستید .

🎤دوستان عزیز .. مصاحبه ای ترتیب دادیم با آقای آشناگر ، دبیر انجمن علمی زبان انگلیسی دانشگاه گیلان و دبیر کل انجمن های علمی دانشجویی دانشگاه گیلان ..
ابتدا قصد داشتیم در قالب یک پیام صوتی این رو تقدیم شما کنیم ولی به دلیل اینکه خواستیم دسترسی به پاسخ های ایشون برای شما راحت تر باشه ، هر سوال رو به صورت متنی و جواب اون سوال رو به صورت فایل صوتی تقدیم شما میکنیم . به زودی هم انشاءالله صورت کامل و متنی این مصاحبه رو در وبسایت انجمن علمی علوم کامپیوتر قرار میدیم .
با ما همراه باشید