زمان کنونی: ۲۶ شهریور ۱۴۰۰, ۰۱:۴۹ ق.ظ مهمان گرامی به انجمن مانشت خوش آمدید. برای استفاده از تمامی امکانات انجمن می‌توانید عضو شوید.
گزینه‌های شما (ورودثبت نام)

نحوه محاسبه پیچیدگی زمانی روشهای جستجو

subtitle
ارسال:
  

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)
ممنون میشم کمک کنید
بعضی جاها هم اومده تو مثال های دیگه از سیگما E استفاده کرده که باز نمیدونم چطوری باید ازش استفاده کنم و چطور حلش کنم

۰
ارسال:
  

hkarimi پاسخ داده:

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

سلام به دوست گلم، مهندس dezchilds
دوستان این بنده خدا راهنمایی میخواستا‌! !‌! بیخی (= بیخیال) Big Grin
من یه توضیح کوچیک میدم. از حلقه های for پاسکال شروع میکنم. چون کلا همیشه به تعداد {( انتها منهای ابتدا )به اضافه یک } بار اجرا میشن. درسته؟؟؟ دقت کن که گفتم "اجرا"
اگه گرفتی که خیلی خوبه.Smile
ولی وقتی حلقه تموم میشه‌، چه اتفاقی میفته؟ بذا با مثال بریم جلو. حلقه زیر رو نگا کن:
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ه که از ۱ تا ۵ اجرا میشه. خود ۱ و ۵ هم اجرا میشن ها.Smile
امیدوارم که گره از کارت باز شده باشه.
موفق باشی

۱
ارسال:
  

fatima1537 پاسخ داده:

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

(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)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; i<=n; i++)
for(j=0; j<=n-1; j++)
z=z+1;
خوب مثلآ جواب این رو داده
o(n ^2) و کلی n نوشته من نمیدونم این n‌ها از کجا میان مثلآ واسه for اولی نوشته n+1 و واسه دومی نوشته n(n+1)
درمورد این قطعه برنامه هم باید گفت که ۲ تا حلقه تو در تو داریم خوب مسلما وقتی شمارنده حلقه اول مثلا به صورت FOR I=1 TO 2 و شمارنده حلقه دوم به صورت FOR I=1 TO 3 باشه به نظرتون حلقه اول چند مرتبه اجرا میشه و حلقه دوم چند بار؟
حلقه اول ۲ بار و حلقه دوم ۲*۳ یعنی ۶ بار اجرا میشه
درضمن یه نکته دیگه هم که الان به چشمم خورد اینه که شما به اعداد شروع و پایان شمارنده دقت نکردید
حلقه اول از ۱ تا N و حلقه داخلی از ۰ تا N-1 t خوب حالا حلقه اول چند بار چک میشه؟N+1 بار و حلقه دوم N بار
فکر کنم به جای N اگر عدد دلخواهی بگذارید و بعد محاسبه کنید مشکلتون حل میشه
(۰۶ آذر ۱۳۹۰ ۱۲:۵۳ ق.ظ)dezchilds نوشته شده توسط:  بعضی جاها هم اومده تو مثال های دیگه از سیگما E استفاده کرده
من خودمم با این عدد e مشکل دارمSmile
البته hkarimi کامل توضیح دادن، من هم برداشت خودم رو از سئوالتون نوشتم



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  مبحث جستجوهای محلی Elham_tm ۶ ۲,۲۱۹ ۲۱ بهمن ۱۳۹۹ ۰۴:۳۱ ب.ظ
آخرین ارسال: mohammadasadi1
  دو سوال در مورد درخت BST(درخت جستجوی دودویی) امیدوار ۳ ۲,۵۶۴ ۱۰ دى ۱۳۹۹ ۱۲:۰۴ ق.ظ
آخرین ارسال: marzi.pnh
  زمان جستجوی درخت fateme.sm ۰ ۳۹۵ ۰۶ دى ۱۳۹۹ ۱۰:۴۱ ب.ظ
آخرین ارسال: fateme.sm
  حل مساله مرتبه زمانی حلقه های تو در تو sarashahi ۱۶ ۱۲,۱۱۷ ۱۹ خرداد ۱۳۹۹ ۰۱:۱۶ ب.ظ
آخرین ارسال: gillda
  محاسبه ارتفاع درخت.... baharkhanoom ۳ ۴,۳۷۴ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۸ ب.ظ
آخرین ارسال: mohsentafresh
  مرتبه زمانی Sanazzz ۱۷ ۹,۰۹۵ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  در جستجوی اساتید امنیت wskf ۰ ۷۷۶ ۱۸ فروردین ۱۳۹۹ ۰۸:۴۶ ب.ظ
آخرین ارسال: wskf
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۶۳۵ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۱,۷۲۶ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  جستجو و ارتباط بین جداول aryana25000 ۰ ۷۱۷ ۰۳ آبان ۱۳۹۸ ۱۰:۳۸ ب.ظ
آخرین ارسال: aryana25000

پرش به انجمن:

Can I see some ID?

به خاطر سپاری رمز Cancel

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close

رمزت رو فراموش کردی؟

Feeling left out?


نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. close