سلام به دوستان و عرض تبریک به کسایی که امسال قبول شدن
من پارسال امتحان دادم و رتبم ۱۳۰۰ آی تی شد
...... یکی از موضوعاتی که من توش می لنگیدم و همچنان هم می لنگم این بحث مرتبه اجرایی و تحلیل پیچیدگیه
کتاب و جزوه هم زیاد خوندم ولی چیز زیادی دستگیرم نشده اگه از دوستان کسی هست که این مبحثو بلده به زبون ساده به ما بگه جریان چیه ....
ممنون از همه دوستان
من نمیدونم چی بگم . والا زیاد سخت نیست . من خودم هیچی بلد نبودم یعنی تو دانشگاه استادمون ما رو دور زد ، و خودم کتاب ساختمان داده مقسمی اون مو قع کارشناسی رو گرفتم و فصل اولشو خوندم نصف موضوع کاملا واسم جا افتاد و مرتبه ها رو به نظر من کتاب قدسی هم خوب گفته. الانم که Clrs رو خوندم کلا موضوع واسم جا افتاد. نظر من اینه که یه نگا به یکی از کتابای ساختمان مقسمی فصل پیچیدگی زمانی بنداز ، ان شاالله واست روشن میشه ، فقط این دید (view( خودتو مثبت کن ، هیچی نیست ، زیادی بزرگ تصورش نکن . امیدوارم مفید باشه.
من چیزی که به ذهنم میرسه واستون میگم اما بهتره یه سوالی که اشکال دارید ازش بپرسید تا با حل اون سوال متوجه بشید.
دنیای واقعی رو در نظر بگیرید : فرض کنید من به شما یک دستور آشپزی میدم که ۲۰ مرحله داره مثلا برنج رو آبکش کنید، لوبیا رو از شب قبل خیس کنید و ..... (۲۰ مرحله)
خوب برای یک آشپز این مراحل زیاده و اون میگه که این دستور زمان زیادی میبره.
توی کامپیوتر هم همینه ما یک الگوریتم (مجموعه دستورات) داریم که باید مو به مو اجرا کنیم حالا اگر تعداد این دستورات زیاد باشه الگوریتم پیچیده است و مرتبه زمانی بالایی داره.
حالا یک سری الگوریتم ها هستند که تعداد دستورات ثابتی دارن که میگن مرتبه خطی هست یک سری هست تعداد دستورات به ورودی بستگی داره مثلا میگه به تعداد ورودی بار به متغییر یک واحد اضافه کن پس هر چه ورودی بیشتر بشه مراحل هم بیشتر میشه اما به تعداد خود ورودی بستگی داره o(n حالا اگه بگه به تعداد مربع ورودی بار به متغییری یک واحد اضافه کن اونوقت تعداد مراحل تابعی از مربع ورودی هست یعنی از مرتبه n^2 (وقتی n ورودی باشه)
[tex]for(i=1,i<=10,i ) y ;[/tex]
خوب این الگوریتم به ورودی بستگی نداره و ۱۰ بار اجرا میشه.
[tex]for(i=1,i<=n,i ) y ;[/tex]
این مورد بسته به ورودی n به تعداد n بار اجرا میشه هر چه n بیشتر باشه مدت اجرای الگوریتم بیشتر است.
[tex]for(i=1,i<=n^{2},i ) y ;[/tex]
این مورد بسته به ورودی n به تعداد n^2 بار اجرا میشه هر چه n بیشتر باشه مدت اجرای الگوریتم بیشتر است.
برای بحث پیچیدگی ها علاوه بر این پست هایی که دوستان گفتن، باید مقداری هم از سری ها در ریاضیات و
دنباله و تصاعد بلد باشید، مثلا باید بدونید که n = n*(n+1) /2 + ....+ سه + دو + یک.
شاید قسمت سختش همون تابع مولد باشه که اگه کار کنی راحت دستت میاد که باید چکار کنی. تمرین، فقط تمرین.
من هم زیاد تو این مبحث قاطی میکنم
میشه به این سوال من جواب بدید
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمی‌باشید. جهت مشاهده پیوندها ثبت نام کنید.
برای شروع و اشنایی با مبحث روابط بازگشتی و مرتبه زمانی
کتاب مرجع : فقط نیپولیتان
کتاب تست : ساختمان مقسمی + الگوریتم سپاهان ( خیلی عالیه اما یه مقدار سنگین هست ولی به جراءت از همه کتابا حتی برای این فصلش از CLRS هم بهتره )