سوال در مورد درس طراحي الگوريتم و ساختمان داده ها

[dezchilds]

سلام دوستان شديدا به كمكتون نياز دارم ، متاسفانه تو درس طراحي الگوريتم ها يه سري اشكالاتي دارم كه فكر ميكنم به دست شما حل بشه .
يه سري الگوريتم ها هست مثل جست و جوي دودويي و باينري و مرتب سازي كه نياز به درك دارند ، تو درك و فهميدن اين ها هيچ اشكالي ندارم و ميتونم تحليلشون كنم ولي مشكل من توي محاسبه پيچيدگي زماني و فرمول ها هست ، آخه اصلآ نميدونم اين 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)
ممنون ميشم كمك كنيد

[soorena]

سلام
محاسبه پيچيدگی زمانی يکی از مهمترين مبحث ها و البته جالب ترين در طراحی الگوريتم هستش.
فکر ميکنم بهترين راه فهميدنشون از تو سايت ويکيپديا باشه که اگه گوگل بزنی حتماً پيدا ميکنی.
http://en.wikipedia.org/wiki/Time_complexity
مرتبه اجرايی برنامه بالا يا همون پيچيدگی زمانی اون همينطور که گفتی (O(n^2 هستش (چرا؟؟؟)
دستور شماره 1 همانطور که ميبينی n+1 بار تکرار ميشه . دستور شماره 2 به ازای هر يک بار اجرا شدن دستور اولی n بار اجرا ميشه
که پس ميشه(n(n+1 .
دستور شماره 3 هم که به تعداد حلقه شماره 2 يعنی n-1 بار اجرا ميشه حال چقدر ميشه اگه همه اينا رو باهم جمع بکنی
چقدر ميشه:::

n + n-1 + n(n+1) =n^2 + 3n -1

خوب مسلما درجه بزرگتر برای ما از همه تو مرتبه زمانی مهم تره پس الگوريتم از مرتبه n^2 يعنی (O(n^2 هستش.
گرفتی؟

[dezchilds]

سلام . خيلي ممنون آره تا حدودي گرفتم ولي خوب چرا حلقه اول شده n+1 بار ؟ ما كه تو حلقه اول از 1 داريم تا n .جريانش چيه ؟ يا حلقه دوم در حالي كه از 0 تا n-1 هست ولي n(n+1) بار اجرا شده . اصلا چرا n+1 ? چرا خود n تنهايي رو ننوشتيم
؟
ببخشيد خيلي سوال بي ربط ميپرسم نه ؟
راستي تو جزوه ما اينو اينطوري حساب كرده

Tn=n+1+n ^2+n+n^2 =2n^2+2n+1

ولي جوابش همون o(n^2)

شده

راستي تو محاسبه بالا اون n كه بولدش كردم از كجا اومد ؟
بعضي جاها هم اومده تو مثال هاي ديگه از سيگما E استفاده كرده كه باز نميدونم چطوري بايد ازش استفاده كنم و چطور حلش كنم

[soorena]

سلام
اولاً خيلی خودت رو درگير ضريب ها نکن چون هيچ اهميتی تو محاسبه پيچيدگی نداره مثلاً مرتبه زمانی يه برنامه که
6*n هستش همون O(n) در نظر گرفته ميشه.اين از اين.
حلقه اول n بار حلقه دوم رو اجرا ميکنه ولی خودش n+1 بار اجرا ميشه تا بار آخر چک بکنه و خارج بشه.
همين روند رو برای حلقه دوم در نظر بگير.
فکر کنم ديگه مشکل حال بشه.
در مورد اون سيگما هم مثال بزن تا برات بگم.

[dezchilds]

سلام مجدد یه سوال دارم فرق >= با = تو حلقه for چیه ؟
در هر دو حالت که ما تا همون عدد میریم مثلآ

for (i=0;i<=5; i++)

تو این دستور ما از 0 تا 5 میریم که میشه 6 بار تکرار حلقه و 6 بار اجرای دستور

for (i=0;i=5; i++)

توی اینم همینه م از 0 تا 5 میریم پس چه لزومی داره از > استفاده کنیم ؟

[مسعود اقدسی فام]

سلام مجدد یه سوال دارم فرق >= با = تو حلقه for چیه ؟
در هر دو حالت که ما تا همون عدد میریم مثلآ

for (i=0;i<=5; i++)

تو این دستور ما از 0 تا 5 میریم که میشه 6 بار تکرار حلقه و 6 بار اجرای دستور

for (i=0;i=5; i++)

توی اینم همینه م از 0 تا 5 میریم پس چه لزومی داره از > استفاده کنیم ؟

مطمئنید کد دوم مثل کد اول عمل می‌کنه؟ امتحان کردید؟ بدنه چیه؟ شاید اونجا کاری کردید که این کد درست کار کرده. وگرنه این دو تا کد مثل هم نیستن. پایینی یه حلقه‌ی بی‌نهایت درست می‌کنه.

[elsin91]

سلام میشه جواب این سوالارو برام بفرستین نیاز فوری دارم
مرسی
1-فرض کنیددر یک الگوریتم داشته باشیم T(n) مساوی o(n) به توان 2 به ازای n=1000 در زمان 30s و برای n=2000 در زمان 2 min اجرا می گردد. به ازای مدت زمان 4 دقیقه مقدار ورودی یعنی n را محاسبه کنید. 2- الگوریتمی با اندازه 15 و مرتبه اجرایی o(n) به توان 2 روی کامپیوتری در مدت زمان 4ms اجرا می گردد. این الگوریتم با اندازه 150 روی همان کامپیوتر در چند میلی ثانیه اجرا می گردد؟