سلام دوستان شدیدا به کمکتون نیاز دارم، متاسفانه تو درس طراحی الگوریتم‌ها یه سری اشکالاتی دارم که فکر میکنم به دست شما حل بشه .
یه سری الگوریتم‌ها هست مثل جست و جوی دودویی و باینری و مرتب سازی که نیاز به درک دارند، تو درک و فهمیدن این‌ها هیچ اشکالی ندارم و میتونم تحلیلشون کنم ولی مشکل من توی محاسبه پیچیدگی زمانی و فرمول‌ها هست، آخه اصلآ نمیدونم این T(n) و این چیزا رو چطوری مینویسن و باید چطوری محاسبه کرد واسه همین رفتم کتاب طراحی الگوریتم‌ها رو خریدم مال جعفر نژاد قمی ولی اونجا هم ازنحوه محاسبه پیچیدگی زمانی‌ها توضیحات زیادی نداده، رفتم کتاب ساختمان داده های مقسمی رو گرفتم بازم چیزی نبود . خلاصه گیج شدم چطوری میتونم تحلیل این الگوریتم‌ها رو انجام بدم مثلآ بعضی جاها میاد n(log 2) مثلآ این لوگ از کجا اومده ؟ کارش چیه ؟ کلآ تو باغشون نیستم چطوری میتونم روش های حل رو یاد بگیرم ؟؟؟؟
مثلا یه جا داده
نقل قول:for (i=1; i<=n; i++)
for(j=0; j<=n-1; j++)
z=z+1;
خوب مثلآ جواب این رو داده
o(n ^2) و کلی n نوشته من نمیدونم این nها از کجا میان مثلآ واسه for اولی نوشته n+1 و واسه دومی نوشته n(n+1)
ممنون میشم کمک کنید
بعضی جاها هم اومده تو مثال های دیگه از سیگما E استفاده کرده که باز نمیدونم چطوری باید ازش استفاده کنم و چطور حلش کنم
سلام به دوست گلم، مهندس dezchilds
دوستان این بنده خدا راهنمایی میخواستا! !! بیخی (= بیخیال)
من یه توضیح کوچیک میدم. از حلقه های for پاسکال شروع میکنم. چون کلا همیشه به تعداد {( انتها منهای ابتدا )به اضافه یک } بار اجرا میشن. درسته؟؟؟ دقت کن که گفتم "اجرا"
اگه گرفتی که خیلی خوبه.
ولی وقتی حلقه تموم میشه، چه اتفاقی میفته؟ بذا با مثال بریم جلو. حلقه زیر رو نگا کن:
For i= 1 to n do
کنترل برنامه میاد دور اول (i=1) رو اجرا میکنه. بعد دور دوم بعد سوم و ... تا nمین دور. ولی به نظرت چجوری بفهمه که حلقه تموم شده؟ همینجور هردمبیل نیس که. بالاخره یه شرطی رو بررسی میکنه که i بزرگتر از n نشده باشه. همین بررسیه هس که بعد از n بار اجرای حلقه باعث میشه بررسی رو n+1 در نظر بگیریم. یعنی در واقع این خطی که نوشتم n+1 بار اجرا میشه. گرفتی؟ بذا همین مثالو تو C بزنم. همون حلقهه به شکل زیر در میاد:
For( i=1; i<=n ; ++i)
یکم توضیح اضافه درباره حلقه: تو اولین دور i=1 میشه و شرط چک میشه. یعنی قسمت سوم (همون i++) بررسی نمیشه. اوکی؟
تو دور دوم، بخش سوم (یعنی i++) اجر شده و بعدش شرط چک میشه. و دیگه تا آخرش همینجور پیش میره.
خب، حالا اگه مثلا حلقه از ۱ تا ۳ باشه،
۱) i=1 میشه و چون شرط درسته وارد حلقه میشه.
۲) i++ اجرا شده و بعد شرط چک میشه که درسته پس وارد حلقه میشه.
۳) i++ اجرا شده و بعدشم شرط. و چون درسته وارد حلقه میشه.
۴) i++ اجرا شده و شرظ بررسی میشه. ولی چون دس نیس دیگه دستورات توی حلقه رو اجرا نمیکنه.
پس گرفتیم که "دستورات" حلقه ۳ بار اجرا میشه ولی اون خطه که حلقه هس، ۴ بار اجرا میشه.
فک کنم ب این همه توضیحی که دادم متوجه شده باشی.
دقت کن که توی C حلقه های زیر با هم متفاوتن:
For( i=0; i<n; i++) ===========> "n" time run block on loop but "n+1" time check
For (i=1; i<n; i++) ===========> "n-1" time run block of loop but "n" time check
for (i=0; i<=n; i++) =======>"n+1" time run block of loop but "n+2" time check
For (i=1; i<=n; i++)===========> "n" time run block of loop but "n+1" time check
سیگما هم دقیقا مث for میمونه دیگه. یکم دقت کنی میبینی که مثلا سیگما از ۱ تا ۵ معادل یه Forه که از ۱ تا ۵ اجرا میشه. خود ۱ و ۵ هم اجرا میشن ها.
امیدوارم که گره از کارت باز شده باشه.
موفق باشی
(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)dezchilds نوشته شده توسط: اصلآ نمیدونم این T(n) و این چیزا رو چطوری مینویسن و باید چطوری محاسبه کردt(n) رو به این صورت محاسبه میکنن که، در هر الگوریتمی خط به خط تعداد دفعاتی که یک دستور اجرا میشه رو مینویسن و بعد این مراحل رو با هم جمع میکنن که اون مقدار میشه t(n)
مثلا الگوریتم زیر
function x(int a,int n)
s=1
for i=1 to n
s=s*a
return(s)
پیچیدگی زمانی خطوط: خط اول ۱،خط دوم ۱، خط سوم n+1(چون شرط حلقه n+1بار چک میشه)، خط چهارم n (چون وقتی که مرتبه n+1ام شرط چک میشه دیگه وارد حلقه نمیشیم)، خط پنچم ۱ هست
که در مجموعt(n)=1+n+1+n+1=2n+3
(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)dezchilds نوشته شده توسط: بعضی جاها میاد n(log 2) مثلآ این لوگ از کجا اومده ؟وقتی که حلقه تکرار شما طوری باشه که به تعداد n بار اجرا نشه بلکه به صورت ضریبی از N اجرا بشه پیچیدگی رو به صورت لگاریتمی مینویسن
به عبارتی وقتی که تعداد مرتبه های زمانی اجرای یک دستور برابر جذری از N باشه
(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)dezchilds نوشته شده توسط: مثلا یه جا دادهدرمورد این قطعه برنامه هم باید گفت که ۲ تا حلقه تو در تو داریم خوب مسلما وقتی شمارنده حلقه اول مثلا به صورت FOR I=1 TO 2 و شمارنده حلقه دوم به صورت FOR I=1 TO 3 باشه به نظرتون حلقه اول چند مرتبه اجرا میشه و حلقه دوم چند بار؟
نقل قول:خوب مثلآ جواب این رو دادهfor (i=1; i<=n; i++)
for(j=0; j<=n-1; j++)
z=z+1;
o(n ^2) و کلی n نوشته من نمیدونم این nها از کجا میان مثلآ واسه for اولی نوشته n+1 و واسه دومی نوشته n(n+1)
حلقه اول ۲ بار و حلقه دوم ۲*۳ یعنی ۶ بار اجرا میشه
درضمن یه نکته دیگه هم که الان به چشمم خورد اینه که شما به اعداد شروع و پایان شمارنده دقت نکردید
حلقه اول از ۱ تا N و حلقه داخلی از ۰ تا N-1 t خوب حالا حلقه اول چند بار چک میشه؟N+1 بار و حلقه دوم N بار
فکر کنم به جای N اگر عدد دلخواهی بگذارید و بعد محاسبه کنید مشکلتون حل میشه
(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)dezchilds نوشته شده توسط: بعضی جاها هم اومده تو مثال های دیگه از سیگما E استفاده کردهمن خودمم با این عدد e مشکل دارم
البته hkarimi کامل توضیح دادن، من هم برداشت خودم رو از سئوالتون نوشتم