اولین بار به ازای [tex]i=1[/tex] تعداد تکرار [tex]\frac{n}{2}[/tex] هستش و به ازای [tex]i=2[/tex] تعداد تکرار [tex]\frac{n}{4}[/tex] هستش و به همین ترتیب.j در هر بار به اندازه [tex]\frac{n}{2}[/tex]، ([tex]n[/tex]) تکرار میشه که برای بار دوم همون[tex]\frac{n}{4}[/tex] هستش .اخرش هم مرتبه اجرا همون n میشه.,وقتی لگاریتم درسته که رشد حلقمون لگاریتمی باشه(یعنی شرط حلقه).در صورتی که اینجا اینطور نیستش
نظرتون در مورد این حلقه چیه؟
for(int i=0; i<=n; i/=2)
cout<<"*";
غیر از اینه که چون هر بار بازه داره نصف میشه مرتبه اجراییش میشه log n
الان دقیقا همین اتفاق داره واسه حلقه بیرونی می افته
ببینید تو مثال شما درسته شمارنده هر بار داره نصف میشه پس زمان اجرا [tex]\lg(n)[/tex].ولی تو مثال قبلی شمارنده داره یه واحد هر بار اضافه میشه.یعنی همیشه داریم [tex]i=1[/tex] ،بعدش [tex]i=2[/tex] بعد [tex]i=3[/tex] و همینطور تا زمانی که [tex]i\le n[/tex].درسته؟
حالا ما باید مجموع اجرای [tex]i[/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.
حالا میخوایم مجموع اجرای [tex]i[/tex] ها رو حساب کنیم:
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]
اکی؟توی مثال شما ما مطمئنیم که به ازای هر [tex]n[/tex] اون [tex]n[/tex] به اندازه [tex]\lg(n)[/tex] بار اجرا میشه چون فقط کافیه تعداد باری که شمارنده داره اضافه میشه رو بشماریم و چون شمارنده هم داره لگاریتمی اضافه میشه پس زمان اجرا [tex]\lg(n)[/tex] میشه ولی تو این مثال به ازای هر [tex]i[/tex] رابطه بالا برقراره.
امیدوارم براتون خوب توضیح داده باشم
در ضمن فکر کنم شرط حلقتون باید *(ضرب) باشه نه /(تقسیم).
(۱۹ مرداد ۱۳۹۳ ۰۹:۱۵ ق.ظ)miladcr7 نوشته شده توسط: در ضمن فکر کنم شرط حلقتون باید *(ضرب) باشه نه /(تقسیم).خیلی ممنون توضیحت کامل بود بله شرط حلقه ضربه، حالا اگه حلقمون تودرتو نباشه و به صورت زیر باشه چی میشه؟
for(int i= 1; i<=n; i++) 1
n/=2; 1
یکهای آخر خط را فقط برای این زدم که فونتش به هم نخوره
مرسیییییییییییی
فکر کنم باید از همون مرتبه [tex]\lg(n)[/tex] باشه البته اگه همین یه حلقه منظورته
(۱۹ مرداد ۱۳۹۳ ۰۶:۰۸ ب.ظ)miladcr7 نوشته شده توسط: فکر کنم باید از همون مرتبه [tex]\lg(n)[/tex] باشه البته اگه همین یه حلقه منظورتهآره منظورم همون یه حلقه اس،
حالا می دونید چی گیجم میکنه؟ اینکه توی مثال اول حلقه داخلی داره کار نصف کردن n را انجام میده پس حلقه بیرونی مثل این حلقه تکیه میشه که مرتبش لگاریتمیه
ببین بذار اینطور بگیم.از مثال دوم شروع میکنیم خب:
[tex]for(int\: i=1\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]
[tex]n=\frac{n}{2}[/tex]
{
اینجا کار ما راحته ببین ما بازم برای زمان اجرا ،میخوایم تعداد باری که [tex]x[/tex] اجرا میشه رو به دست بیاریم خب؟
حالا قبول داری به ازای [tex]i=1[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) ۱ بار اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) بازم ۱ بار اجرا میشه؟
تا وقتی که [tex]i>n[/tex] برقرار شه و شرط حلقه رو نقض کنه.اکی؟
حالا برای به دست اوردن زمان اجرا ما باید تعداد این دفعات رو بشماریم خب یا مجموع این [tex][tex]i[/tex][/tex] ها رو به دست بیاریم.حالا دقت کن این بار دیگه اینطور نیست که بگیم مثلا به ازای [tex]i=1[/tex] جمله اصلی [tex]\frac{n}{2}[/tex] تکرار میشه و...
چون گفتیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی ۱ بار فقط اجرا میشه حالا ما میخوایم تعداد این [tex][tex]i[/tex][/tex] رو به دست بیاریم
اگه برای چند عدد تست کنی میبینی که برای هر عدد [tex]n[/tex] تعداد [tex][tex]i[/tex][/tex] برابر [tex]Lg(n)[/tex] میشه پس زمان اجرا هم [tex]Lg(n)[/tex] میشه.هر چند با یه خرده دقت میتونستی بفهمی تقسیم شدن عدد [tex]n[/tex] تو این مثال مثل ضرب یا تقسیم شدن شمارندست البته چون یه حلقه داریم ها.
حالا مثال اول. توی مثال اول ما بازم میخوایم مجموع تعداد دفعات اجرای جمله اصلی به ازای هر [tex][tex]i[/tex][/tex] رو به دست بیاریم.دقت کن چون
حلقه تو در تو داریم پس دیگه نمیتونیم بگیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی یه بار اجرا میشه و چون هر بار یه واحد از مقدار [tex]n[/tex] هم با اجرای جمله اصلی کم میشه پس نمیشه گفت به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی [tex]n[/tex] بار تکرار میشه.حالا ما این مجموع رو حساب میکنیم اگه مجموع تعداد دفعات اجرای جمله اصلی [tex]Lg(n)[/tex] شد خب حرف شما قابل قبول.پس ما همیشه برای زمان اجرا مجموع تعداد اجرای جمله اصلی رو حساب میکنیم.
حالا ما باید مجموع اجرای [tex][tex]i[/tex][/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.
حالا میخوایم مجموع اجرای [tex][tex]i[/tex][/tex] ها رو حساب کنیم:
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]
پس زمان اجرا همون [tex]\theta(\: n)[/tex] میشه.
دقت کن که جمله [tex]n--[/tex] باعث شده دیگه نتونیم بگیم مثلا حلقه اول دقیقا این قدر اجرا میشه و حلقه دوم هم به همچنین.اگه
[tex]n--[/tex] نبودش زمان اجرای حلقه رو میتونستیم به دست بیاریم ولی با این شرایط به ازای [tex]i=1[/tex] حلقه دوم یه تعداد بار اجرا میشه و به ازای [tex]i=2[/tex] یه تعداد بار دیگه.پس ما مجبوریم که مجموع این تعداد بارها رو به دست بیاریم
(۲۰ مرداد ۱۳۹۳ ۱۲:۰۳ ب.ظ)miladcr7 نوشته شده توسط: ببین بذار اینطور بگیم.از مثال دوم شروع میکنیم خب:
[tex]for(int\: i=1\: ;\: i<n\: ;\: i )[/tex]
}
[tex]x ;[/tex]
[tex]n=\frac{n}{2}[/tex]
{
اینجا کار ما راحته ببین ما بازم برای زمان اجرا ،میخوایم تعداد باری که [tex]x[/tex] اجرا میشه رو به دست بیاریم خب؟
حالا قبول داری به ازای [tex]i=1[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) ۱ بار اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی( که همون [tex]x 1[/tex] هستش ) بازم ۱ بار اجرا میشه؟
تا وقتی که [tex]i>n[/tex] برقرار شه و شرط حلقه رو نقض کنه.اکی؟
حالا برای به دست اوردن زمان اجرا ما باید تعداد این دفعات رو بشماریم خب یا مجموع این [tex][tex]i[/tex][/tex] ها رو به دست بیاریم.حالا دقت کن این بار دیگه اینطور نیست که بگیم مثلا به ازای [tex]i=1[/tex] جمله اصلی [tex]\frac{n}{2}[/tex] تکرار میشه و...
چون گفتیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی ۱ بار فقط اجرا میشه حالا ما میخوایم تعداد این [tex][tex]i[/tex][/tex] رو به دست بیاریم
اگه برای چند عدد تست کنی میبینی که برای هر عدد [tex]n[/tex] تعداد [tex][tex]i[/tex][/tex] برابر [tex]Lg(n)[/tex] میشه پس زمان اجرا هم [tex]Lg(n)[/tex] میشه.هر چند با یه خرده دقت میتونستی بفهمی تقسیم شدن عدد [tex]n[/tex] تو این مثال مثل ضرب یا تقسیم شدن شمارندست البته چون یه حلقه داریم ها.
حالا مثال اول. توی مثال اول ما بازم میخوایم مجموع تعداد دفعات اجرای جمله اصلی به ازای هر [tex][tex]i[/tex][/tex] رو به دست بیاریم.دقت کن چون
حلقه تو در تو داریم پس دیگه نمیتونیم بگیم به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی یه بار اجرا میشه و چون هر بار یه واحد از مقدار [tex]n[/tex] هم با اجرای جمله اصلی کم میشه پس نمیشه گفت به ازای هر [tex][tex]i[/tex][/tex] جمله اصلی [tex]n[/tex] بار تکرار میشه.حالا ما این مجموع رو حساب میکنیم اگه مجموع تعداد دفعات اجرای جمله اصلی [tex]Lg(n)[/tex] شد خب حرف شما قابل قبول.پس ما همیشه برای زمان اجرا مجموع تعداد اجرای جمله اصلی رو حساب میکنیم.
حالا ما باید مجموع اجرای [tex][tex]i[/tex][/tex] ها رو به دست بیاریم اکی؟
قبول دارید به ازای [tex]i=1[/tex] جمله اصلی به اندازه [tex]\frac{n}{2}[/tex] اجرا میشه؟
و به ازای [tex]i=2[/tex] جمله اصلی به اندازه [tex]\frac{n}{4}[/tex] اجرا میشه؟
و به ازای [tex]i=3[/tex] جمله اصلی به اندازه [tex]\frac{n}{8}[/tex] اجرا میشه؟
و همینطوری تا اخر ادامه پیدا میکنه.
حالا میخوایم مجموع اجرای [tex][tex]i[/tex][/tex] ها رو حساب کنیم:
[tex]\frac{n}{2} \frac{n}{4} \frac{n}{8} ...=n(\frac{1}{2} \frac{1}{4} \frac{1}{8} ...)=n\cdot\frac{\frac{1}{2}}{1-\frac{1}{2}}=n\cdot\frac{\frac{1}{2}}{\frac{1}{2}}=n=\theta(n)[/tex]
پس زمان اجرا همون [tex]\theta(\: n)[/tex] میشه.
دقت کن که جمله [tex]n--[/tex] باعث شده دیگه نتونیم بگیم مثلا حلقه اول دقیقا این قدر اجرا میشه و حلقه دوم هم به همچنین.اگه
[tex]n--[/tex] نبودش زمان اجرای حلقه رو میتونستیم به دست بیاریم ولی با این شرایط به ازای [tex]i=1[/tex] حلقه دوم یه تعداد بار اجرا میشه و به ازای [tex]i=2[/tex] یه تعداد بار دیگه.پس ما مجبوریم که مجموع این تعداد بارها رو به دست بیاریم
آره کاملا توجیح شدم، گرچه هنوز نفهمیدم اشتباه کارم جاست ولی منطق استدلال شما را کاملا متوجه میشوم، (البته فکر کنم من وابستگی حلقه ها را لحاظ نمی کنم) به هر حال ممنونم ازت بابت وقتی که گذاشتی
(۲۱ مرداد ۱۳۹۳ ۰۹:۱۸ ق.ظ)miladcr7 نوشته شده توسط: خواهش میکنم.چه اشتباهی رو متوجه نشدی بگو شاید تونستم کمکت کنم؟
نحوه توضیح دادنت چقد مث من شده
افرین بچه ها که انقدر بهم کمک میکنین، هر وقت میام مانشت احساس خوبه رقابت سالم رو حداقل توو چندتا تاپیک حس میکنم
من چند روزه توو موود ساختمان نیستم
سلام خسته نباشید.اره دیگه ازت یاد گرفتم
فکر کنم بدونم برای چی قاطی کردی.یه چند تا مثال میزنم امیدوارم باعث نشم بیشتر قاطی کنی
.این حلقه رو در نظر بگیر:
[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]\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] و ....
وقتی هم داریم مجموع این تعداد اجراها رو به دست بیاریم در واقع زمان اجرای کل رو داریم به دست میاریم
________________________________________________________________________________________________________
اوه اوه چه زیاد شد ببخشید دیگه.امیدوارم خوب توضیح داده باشم.اگه بازم مشکلی بود بگو تا اگه تونستیم حلش میکنیم و اگه هم نتونستیم از بقیه دوستان کمک میگیریم
سلام دوستان
لطفا اگه کسی میتونه به این سوالم جواب بده. مرسی
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
بله همون الگوریتم جایگشت هستش
(۲۹ مرداد ۱۳۹۳ ۰۶:۴۵ ب.ظ)miladcr7 نوشته شده توسط: بله همون الگوریتم جایگشت هستش
توو تاپیکه خودش یکم توضیح میدی؟ منم گیج شدم
Sent from my iPad using
مهمان عزیز شما قادر به مشاهده پیوندهای انجمن مانشت نمیباشید. جهت مشاهده پیوندها ثبت نام کنید.
چیشو توضیح بدم؟