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

حل مساله مرتبه زمانی حلقه های تو در تو

ارسال:
  

sarashahi پرسیده:

حل مساله مرتبه زمانی حلقه های تو در تو

این مثال از کتاب پوران پژوهش صفحه ۶ هست اما به نظرم یه تیکشو جا انداخته و چاپ نشده:

for (i=1;i<=n;i++)
for(j=1;j<=n;j+=i)

x=x+1;

مگه مرتبه هر خط n نمیشه؟ لطفا جواب کتاب رو هم ببینید.
نقل قول این ارسال در یک پاسخ

۶
ارسال:
  

MiladCr7 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

سلام خسته نباشید
این مثالا رو داشته باش

این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]
{

حالا زمان اجرا:قبول داری حلقه [tex][tex]n[/tex][/tex] بار دستور اصلی ( که همون [tex]x ;[/tex] هستش ) رو اجرا میکنه که این [tex][tex]n[/tex][/tex] بار همون تعداد اجرای شمارنده حلقه( [tex][tex]i[/tex][/tex] ) هم هست درسته؟پس زمان اجرا میشه:[tex]\theta(n)[/tex]

________________________________________________________________________________​______________________-

حالا این حلقه رو در نظر بگیر:

[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<n\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{

حالا زمان اجرا:قبول داری به ازای هر [tex][tex]i[/tex][/tex] حلقه دومی به اندازه [tex][tex]n[/tex][/tex] بار اجرا میشه و متعاقبا جمله اصلی هم [tex][tex]n[/tex][/tex] بار
تکرار میشه؟
ولی یه مسئله ای که باید بهش دقت کنی اینه که به ازای هر [tex][tex]i[/tex][/tex] از حلقه اول، حلقه دومی داره به اندازه ثابتی اجرا میشه درسته؟
پس برای همین ما میتونیم بگیم که طبق اصل شمارش تعداد اجرای دستور اصلی میشه:
به ازای هر [tex][tex]i[/tex][/tex] ،جمله اصلی [tex][tex]n[/tex][/tex] بار تکرار میشه پس به ازای [tex][tex]n[/tex][/tex] بار میشه :[tex]n\ast n[/tex] که
زمان اجرا میشه :[tex]\theta(n^2)[/tex]

ببین حالا نکته اینجاست:وقتی مثلا دو حلقه تو در تو داریم زمانی میتونی تعداد اجرای حلقه بیرونی رو مستقل از حلقه دوم بگی( مثلا بگی حلقه بیرونی [tex][tex]n[/tex][/tex] بار اجرا میشه و حلقه تویی [tex]\lg(n)[/tex] بار) که به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول، حلقه دوم به تعداد [tex]\lg(n)[/tex] بار اجرا بشه که نیازی نباشه مجموع بگیری ولی اگه به ازای هر [tex][tex]i[/tex][/tex] از حلقه اولی ،حلقه دوم به تعداد متغیری اجرا شد دیگه نمیتونی زمان اجرای حلقه اول رو همینطوری مستقل بگی میدونی چرا؟مثال زیر رو داشته باش


[tex]for\: (int\: i=0\: ;\: i<n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<i\: ;\: j )[/tex]
}
[tex]x ;[/tex]
{
{


خب حالا سوال من اینه : حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه درسته؟ ولی ایا میتونی برای محاسبه تعداد دفعات اجرای جمله اصلی بیای
از این روش بری که بگی حلقه اول [tex][tex]n[/tex][/tex] بار تکرار میشه ؟نه نمیتونی چون به ازای هر [tex][tex]i[/tex][/tex] توی حلقه اول ،حلقه دوم داره به یه مقدار متغیر اجرا میشه مثلا به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری.خب الان اگه برای به دست اوردن تعداد دفعه اجرای جمله اصلی بیایم بگیم حلقه اول [tex][tex]n[/tex][/tex] بار اجرا میشه اون وقت برای حلقه دوم چی بگیم؟مگه نباید توی این روش تعداد دفعه اجرای حلقه دوم رو توی تعداددفعه اجرای حلقه اول ضرب کنیم؟ولی میبینی نمیتونیم این کار رو انجام بدیم چون تعداد دفعه اجرای حلقه دوم به ازای هر بار اجرای حلقه اول متغیره اکی؟
پس مجبوریم مجموع تعداد دفعات اجرای حلقه دوم رو به ازای هر بار اجرای حلقه اول محاسبه کنیم که تو این مثال داریم:

به ازای هر [tex][tex]i[/tex][/tex] حلقه دوم از ۱ تا [tex]j[/tex] متغیره و [tex][tex]i[/tex][/tex] بار تکرار میشه.
یعنی به ازای [tex]i=1[/tex] حلقه دوم ۱ بار و به ازای [tex]i=2[/tex] حلقه دوم ۲ بار و همینجوری پس زمان اجرا:

[tex]1 2 3 ... n=\frac{n\ast(n 1)}{2}=\theta(n^2)[/tex]


________________________________________________________________________________​________________
اینم مثال بالایی صفحه ۶ ساختمان داده پوران

[tex]for\: (int\: i=0\: ;\: i<=n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<=n\: ;\: j )[/tex]
}
[tex]x ;[/tex]
[tex]n--;[/tex]
{


حالا توی این مثال اگه بگی حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه برای حلقه دوم چی میگی؟
در ضمن برای حلقه دوم هم دقت کن نمیتونیم بگیم زمان اجراش [tex]\theta(n)[/tex] چون هر بار [tex][tex]n[/tex][/tex] داره عوض میشه پس باید بیایم مجموع این تعداد اجراها رو به دست بیاریم یعنی به ازای [tex]i=1[/tex] حلقه دوم چند بار اجرا میشه و به ازای [tex]i=2[/tex] حلقه دوم چند بار تکرار میشه.ما از این روش استفاده کردیم چون به ازای هر [tex][tex]i[/tex][/tex] تو حلقه اول ،حلقه دوم به مقدار متغیری داره اجرا میشه پس باید مجموع این اجراها رو به دست بیاریم.ولی اگه بگیم حلقه اول [tex]\lg(n)[/tex] بار داره تکرار میشه اون وقت تعداد اجرای حلقه دوم رو نداریم یه بار [tex]\frac{n}{2}[/tex] بار اجرا میشه و یه بار [tex]\frac{n}{4}[/tex] و ....
وقتی هم داریم مجموع این تعداد اجراها رو به دست بیاریم در واقع زمان اجرای کل رو داریم به دست میاریم

________________________________________________________________________________​________________

[tex]for\: (int\: i=0\: ;\: i<=n\: ;\: i )[/tex]

}
[tex]for\: (int\: j=0\: ;\: j<=n\: ;\: j =i)[/tex]
}
[tex]x ;[/tex]
{
اولش برای اینکه بهتر مسئله رو درک کنیم من محدودش میکنم و فرض میکنم [tex]n=8[/tex]
خب؟؟؟؟
حالا این تریس رو داشته باش(میدونیم جمله اصلی [tex]x=x 1[/tex] هستش)

[tex]i=1[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم یکی یکی جلو میره پس جمله اصلی ۸ بار اجرا میشه
[tex]i=2[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم دوتا دوتا جلو میره پس جمله اصلی ۴ بار اجرا میشه
[tex]i=3[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم سه تا سه تا جلو میره پس جمله اصلی ۲ بار اجرا میشه
[tex]i=4[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم چهارتا چهارتا جلو میره پس جمله اصلی ۲ بار اجرا میشه
[tex]i=5[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم پنج تا پنج تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=6[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم شش تا شش تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=7[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم هفت تا هفت تا جلو میره پس جمله اصلی ۱ بار اجرا میشه
[tex]i=8[/tex][tex][tex]\leftarrow[/tex][/tex] شمارنده حلقه دوم هشت تا هشت تا جلو میره پس جمله اصلی ۱ بار اجرا میشه

و الان میتونیم تعداد اجرای جمله اصلی رو اینجوری به دست بیاریم(تعداد اجراهای هر مرحله رو با هم جمع میزنیم):
[tex]8 4 2 2 1 1 1 1[/tex]
جمه بالا رو میتونیم اینجوری هم بنویسیم(حاصل تقسیم رو کف در نظر بگیر)
[tex]\frac{8}{1} \frac{8}{2} \frac{8}{3} \frac{8}{4} \frac{8}{5} \frac{8}{6} \frac{8}{7} \frac{8}{8}[/tex]
خب حالا اگه عدد رو به [tex][tex]n[/tex][/tex] تعمیم بدیم داریم:
[tex]n \frac{n}{2} \frac{n}{3} \frac{n}{4} \frac{n}{5} \frac{n}{6} ... \frac{n}{n}=n(1 \frac{1}{2} \frac{1}{3} \frac{1}{4} ... \frac{1}{n})=\theta(nLog(n))[/tex]

امیدوارم کمکتون کنن اینا
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

به این نکته توجه کنید که حلقه دوم وابسته به حلقه اول هست.ودیگه nنمیشه
خودتونtraceکنید.نشد من حلش میکنم
نقل قول این ارسال در یک پاسخ

ارسال:
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

(۰۴ آذر ۱۳۹۳ ۱۲:۲۱ ب.ظ)software94 نوشته شده توسط:  به این نکته توجه کنید که حلقه دوم وابسته به حلقه اول هست.ودیگه nنمیشه
خودتونtraceکنید.نشد من حلش میکنم
درسته چون حلقه وابسته هست ، حلقه دوم میشه n(n+1)

trace هم به این شکل انجام دادم.
به ازای i=1 ، متغیر j از ۱ تا n تغییر میکنه و دستور ۱ بار اجرا میشه.
به ازای i=2 ، متغیر j از ۱ تا n تغییر میکنه و دستور ۲ بار اجرا میشه و همینطور الی آخر...
اشتباه کارمو بهم بگید ممنون.

مگه برای حلقه های وابسته مث این سوال باید حتما تریس کنیم تا جواب بدست بیاد؟
بدون تریس مگه حلش اینطوری نمیشه که اگه حلقمون =< داشته باشه و i=a باشه تعداد اجرا میشه b-a+1+1 و دستوراتش b-a+1
[/align]
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۱
ارسال:
  

m!r@ پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

فرض کنید تعداد اعداد برابر ۱۰ می باشد. n=10
گام اول: تغییرات حلقه دوم یکی یکی است پس کلا ۱۰ بار تکرار داریم یعنی ۱+۲+۳+ ... +۱۰ => n عدد
گام دوم: تعییرات حلقه دوم دو تا دو تا است پس کلا ۵ بار تکرار داریم(سقف جز صحیح) یعنی ۱+۳+۵+۷+۹ => n/2 عدد
گام سوم: تغییرات حلقه دوم سه تا سه است پس کلا ۴ تکرار داریم(سقف جز صحیح) یعینی ۱ + ۴ +۷+۱۰ => n/3 عدد
گام چهارم: تغییرات حلقه دوم چهار تا چهار است پس کلا ۳ تکرار داریم(سقف جز صحیح) یعنی ۱+ ۵+۹ => n/4 عدد
گام پنجم :تغییرات حلقه دوم پنج تا پنج است پس کلا ۲ تکرار داریم(سقف جز صحیح) یعنی ۱+۶ => n/5 عدد
گام ششم:تغییرات حلقه دوم شش تا شش است پس کلا ۲تکرار داریم(سقف جز صحیح) یعنی ۱+۷ n/6 عدد
گام هفتم:تغییرات حلقه دوم هفت تا هفت است پس کلا ۲ تکرار داریم(سقف جز صحیح) یعنی ۱+۸ n/7 عدد
گام هشتم:تغییرات حلقه دوم هشت تا هشت است پس کلا ۲ تکرار داریم(سقف جز صحیح) یعنی ۱+ ۹ => n/8 عدد
گام نهم: تغییرات حلقه دوم نه تا نه است پس کلا ۲ تکرار داریم(سقف جز صحیح) ۱+ ۱۰ => n/9 عدد
گام دهم : تغییرات حلقه دوم ده تا ده است پس کلا ۱ تکرار داریم(سقف جز صحیح) ۱ n/10 عدد
گام یازدهم خروج از حلقه

نتیجه جمع تعداد اعداد بدست امده یعنی n+n/2+n/3+n/4+...n/10
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

نه چون وابسته است نمیشه n+1)n)
باید به ازای هربار اجرای حلقه دوم که اجرا میشه همه رو با هم جمع بزنی که یه تصاعد میشه جواب اون تصاعد میشه جواب اخرت.
دوباره traceکنSmile

اینو ببین
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

توی کتاب برای حلقه های وابسته گفته حلقه دوم میشه: n(n+1)
نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

اینو ببین


فایل‌(های) پیوست شده

نقل قول این ارسال در یک پاسخ

۰
ارسال:
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

چرا n تقسیم بر ۲ میشه؟ من همین نمیفهمم.
نقل قول این ارسال در یک پاسخ

ارسال: #۱۰
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

(۰۴ آذر ۱۳۹۳ ۰۱:۵۹ ب.ظ)sarashahi نوشته شده توسط:  چرا n تقسیم بر ۲ میشه؟ من همین نمیفهمم.

واسه اینکه بار اول گام زمانی یک پس nبار اجرا میشه.بار دومکه گام زمانی میشه ۲قبول داری دوتا دوتا میره جلو پس میشهn/2بار بعد که گام زمانی میشه ۳اونوقت سه تا سه تامیره جلو
حله؟Smile
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۱
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

نه نمیفهمم چرا باید تقسیم بشه. وقتی j میشه ۲ پس n هم میشه ۲ بار.درسته؟
نقل قول این ارسال در یک پاسخ

ارسال: #۱۲
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

(۰۴ آذر ۱۳۹۳ ۰۲:۰۷ ب.ظ)sarashahi نوشته شده توسط:  نه نمیفهمم چرا باید تقسیم بشه. وقتی j میشه ۲ پس n هم میشه ۲ بار.درسته؟
ببین میدونی گام چیه؟وقتی گام یک حلقه یکی یکی میره جلو.وقتی گام دو حلقه دوتا دتا میره جلو.وقتی دوتا دوتا بره خب مسلما نصفه nاجرا میشه.الان کجایه این مبهمه؟
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۳
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

تفاوتش با این برنامه چیه؟ چون الان من این برنامه زیر رو کاملا میفهمم:

for i=1 ; i=<n ; i++
for j=i ; j =<n ; j++

x=x+1;
اینجا بار اول n بار انجام میشه
بار دوم n-1 بار چون : n-2+1
بار سوم n-2 و ...

ضمنا من مرتبه زمانی رو اینجوری یاد گرفتم
برای خود حلقه وقتی =< داره میشه b-a+1+1 اگه نداشته باشه b-a+1
برای اجرای دستور داخلیش b-a+1 و b-a
با این روش من اصلا نمیفههم چرا باید تقسیم بشه؟
نقل قول این ارسال در یک پاسخ

ارسال: #۱۴
  

software94 پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

(۰۴ آذر ۱۳۹۳ ۰۳:۰۶ ب.ظ)sarashahi نوشته شده توسط:  تفاوتش با این برنامه چیه؟ چون الان من این برنامه زیر رو کاملا میفهمم:

for i=1 ; i=<n ; i++
for j=i ; j =<n ; j++

x=x+1;
اینجا بار اول n بار انجام میشه
بار دوم n-1 بار چون : n-2+1
بار سوم n-2 و ...

ضمنا من مرتبه زمانی رو اینجوری یاد گرفتم
برای خود حلقه وقتی =< داره میشه b-a+1+1 اگه نداشته باشه b-a+1
برای اجرای دستور داخلیش b-a+1 و b-a
با این روش من اصلا نمیفههم چرا باید تقسیم بشه؟

تفاوتش اینه که اینجا j هیچ ربطی به i نداره.گام زمانی دو حلقه مربوط به خودشون وحلقه دوم داخل حلقه اول هست وبه ازای هربار iکه تو حلقه اول افزایش پیدا میکنه حلقه دوم دوباره از اول شروع میشه تا حلقه اول بشه n.فکر کنم این مباحثو باید حسابی روش تمرکز کنی.یک کم به گامها ونوع حلقه ها توجه کن.
یافتن تمامی ارسال‌های این کاربر
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۵
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

اونکه i از j مستقل هست توی پست اول رو که خودمم میدونم.
مساله ما یه حلقه وابسته هست درسته؟
از طریق اون فرمولی که نوشتم میتونیم جوابو بدست بیاریم یا حتما باید تریس کنیم؟
اگه باید حتما تریس بشه میشه تریسش رو به شکلی که هم i باشه هم j هم تعداد اجرای دستور اصلی برام بنویسید.
چون بدون شکل من اصلا نمیفهممConfused
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۶
  

sarashahi پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

نه منظورم اینه که برای i یک ستون ، برای j یک ستون و برای اجرای دستور هم یک ستون داشته باشیم تا تغییراتش رو بفهمیم.
نقل قول این ارسال در یک پاسخ

۰
ارسال: #۱۷
  

gillda پاسخ داده:

RE: حل مساله مرتبه زمانی حلقه های تو در تو

for(int i=1; i<=n;i++)
for(int j=1;j<=n;j=j )

x=x+1;

در اینجا چجوری باید مرتبه زمانی رو حساب کرد؟
نقل قول این ارسال در یک پاسخ



موضوع‌های مرتبط با این موضوع...
موضوع: نویسنده پاسخ: بازدید: آخرین ارسال
  جزوه اسکن شده " سیستم های توزیع شده " دکتر پدرام arash691 ۸ ۱۵,۰۳۸ ۱۰ آذر ۱۴۰۱ ۰۲:۵۵ ق.ظ
آخرین ارسال: negarrah
Exclamation سلام لطفاً یکی به من بگه مرتبه زمانی ها چطوری به log تبدیل میشن فرمول داره؟؟ Azadam ۶ ۴,۹۸۹ ۰۶ دى ۱۴۰۰ ۰۹:۰۲ ق.ظ
آخرین ارسال: Soldier's life
  مرتبه ایجاد درخت rad.bahar ۱ ۳,۴۰۵ ۳۰ مهر ۱۳۹۹ ۰۳:۳۴ ب.ظ
آخرین ارسال: rad.bahar
  مرتبه شبه کد rad.bahar ۱ ۲,۳۶۱ ۲۲ مهر ۱۳۹۹ ۰۹:۳۲ ب.ظ
آخرین ارسال: BBumir
  دانلود وویس درس سیستم های توزیعی دکتر پدرام x86 ۴۴ ۴۲,۰۸۴ ۲۱ خرداد ۱۳۹۹ ۰۸:۳۱ ب.ظ
آخرین ارسال: محسن افضلی
  مرتبه زمانی Sanazzz ۱۷ ۲۱,۷۱۲ ۰۹ اردیبهشت ۱۳۹۹ ۰۶:۴۶ ب.ظ
آخرین ارسال: mohsentafresh
  پیچیدگی زمانی اکشن های قابل اعمال در یک وضعیت اsepid8994 ۰ ۱,۸۰۸ ۲۹ اسفند ۱۳۹۸ ۱۲:۵۱ ب.ظ
آخرین ارسال: اsepid8994
  پایتون (طراحی وب یا دیتا ساینس؟) مساله این است... sirvan.t ۲ ۳,۶۸۲ ۱۹ بهمن ۱۳۹۸ ۱۲:۰۱ ب.ظ
آخرین ارسال: sirvan.t
  مرتبه زمانی یافتن قطر Sepideh96 ۲ ۳,۸۳۳ ۰۸ آذر ۱۳۹۸ ۰۴:۳۴ ب.ظ
آخرین ارسال: erfan30
  مرتبه مانی Sanazzz ۳ ۳,۷۴۹ ۰۵ خرداد ۱۳۹۸ ۰۲:۳۶ ب.ظ
آخرین ارسال: Sanazzz

پرش به انجمن:

Can I see some ID?

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

Feeling left out?


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

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

Feeling left out?


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