جواب دقیقش که میشه
$(3n 1)*C(n 2,3)/4$
اما اینکه از نظر مرتبه اجرا تقریبا برابر چی میشه را راحت میشه از روی تست ها انتخاب کرد

(۲۳ مرداد ۱۳۹۳ ۰۸:۱۹ ق.ظ)shayesteb نوشته شده توسط:  سلام دوستان

میشه توضیح بدید تریس مربوط به الگوریتم زیر چطوری میشه و زمان اجراش چقدر هست؟



to n $sum\: \longleftarrow\: 1\: \:$
$for\: \: \: i\longleftarrow1\: to\: n$
$do\: for\: \: \: j\longleftarrow1\: to\: i^2$
$do\: if\: \: j\: \mod\: i=0$
$then\: for\: k\longleftarrow1\: to\: j$
$do\: sum\: \longleftarrow\: sum\: 1$

دوستان ممنون میشم اگه راهنمایی کنید

میشه بگی خط اول چیکار میکنه؟

(۲۳ مرداد ۱۳۹۳ ۰۶:۰۲ ب.ظ)miladcr7 نوشته شده توسط:  میشه بگی خط اول چیکار میکنه؟

اشتباه شده بود . الان درست شد . sum=1 قرار داده میشه.

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

(۲۳ مرداد ۱۳۹۳ ۰۷:۰۵ ب.ظ)miladcr7 نوشته شده توسط:  زمان اجراشو نمیدونی که حداقل جوابامون رو باهاش چک کنیم ببینیم درسته یا نه؟

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

داره فکر کنم.خودت حلش نکردی؟

این جواب چجوری به دست اومده؟

پس حلقه K چی میشه؟

دوستان ممنون از اینکه راهنمایی کردین

پاسخش تتا n به توان ۴ هستش ( سوال ۴۴ فصل اول کتاب ۶۰۰ تست البته من هم نمیدونستم بعدا یکی از دوستان راهنمایی کردن ) اگه هم کسی خواست بگه تا جواب را توضیح بدم.

---

(۲۳ مرداد ۱۳۹۳ ۰۸:۲۹ ب.ظ)a.kam نوشته شده توسط:  جواب دقیقش که میشه
$(3n 1)*C(n 2,3)/4$
اما اینکه از نظر مرتبه اجرا تقریبا برابر چی میشه را راحت میشه از روی تست ها انتخاب کرد

دوست عزیز ممنونم

ای ول منم $\theta(n^4)$ رو به دست اوردم.ببخشید البته صبح حسابش کردم ولی خب شک داشتم دیگه نگفتم.ولی سوال خیلی جالبی بود.البته من از تریس کردن و تصاعد عددی به دستش اوردم.راه حل دیگه ای داره رو نمیدونم

(۲۴ مرداد ۱۳۹۳ ۱۲:۳۹ ق.ظ)miladcr7 نوشته شده توسط:  ای ول منم $\theta(n^4)$ رو به دست اوردم.ببخشید البته صبح حسابش کردم ولی خب شک داشتم دیگه نگفتم.ولی سوال خیلی جالبی بود.البته من از تریس کردن و تصاعد عددی به دستش اوردم.راه حل دیگه ای داره رو نمیدونم

بله از طریق تریس کردن به دست میاد. آفرین که جوابتون درست بوده

(۲۴ مرداد ۱۳۹۳ ۰۹:۱۸ ق.ظ)shayesteb نوشته شده توسط:  

(24 مرداد ۱۳۹۳ ۱۲:۳۹ ق.ظ)miladcr7 نوشته شده توسط:  ای ول منم $\theta(n^4)$ رو به دست اوردم.ببخشید البته صبح حسابش کردم ولی خب شک داشتم دیگه نگفتم.ولی سوال خیلی جالبی بود.البته من از تریس کردن و تصاعد عددی به دستش اوردم.راه حل دیگه ای داره رو نمیدونم

بله از طریق تریس کردن به دست میاد. آفرین که جوابتون درست بوده

مرسی ممنون

ببین زمان اجرای حلقه دوم و سوم $\lg(n)$ نمیشه چون به ازای هر $j$ توی حلقه دوم مقدار $k$ توی حلقه سوم فرق داره درسته؟
یعنی وقتی $j$ مقدارش ۱ باشه حلقه سوم ۱ بار اجرا میشه و وقتی $j=2$ باشه حلقه سوم ۲ بار اجرا میشه و وقتی $j=4$ باشه حلقه سوم ۴ بار اجرا میشه پس لگاریتمی تغییر نمیکنه.
حالا این تریس رو داشته باش:

$j=1\longrightarrow1$

$j=2\longrightarrow2$

$j=4\longrightarrow4$

$j=8\longrightarrow8$

و همینطوری ادامه بده.حال قبول داری $j$ داره به صورت $2^p$ تغییر میکنه.p از صفر شروع میشه.حالا این اجرا تا چه وقتی
ادامه پیدا میکنه؟
تا وقتی که $2^p<n$ درسته؟یعنی وقتی که $2^{p 1}>n$ دیگه حلقه اجرا نمیشه.درسته؟
پس ما میتونیم یه تقریب بزنیم به این صورت که:$2^{p}\cong n$ درست؟
حالا مجموع زمان اجراها رو محاسبه میکنیم:
$2^0 2^1 2^2 2^3 ... 2^p=\frac{2^{p 1}-1}{2-1}=2^{p 1}-1\cong n=\theta(n)$

حلقه اول هم که $\lg(n)$ پس زمان اجرای کل:$n.\lg(n)$

---

اینجوری حلش کردم با تریس.یه عدد مثل ۴ رو در نظر گرفتم اینم از تریس:

$i=1\rightarrow j=1\rightarrow1$:::::::یعنی به ازای $i=1$ و $j=1$ یه بار اجرا میشه

$i=2\rightarrow j=2\rightarrow2$

$i=2\rightarrow j=4\rightarrow4$

$i=3\rightarrow j=3\rightarrow3$

$i=3\rightarrow j=6\rightarrow6$

$i=3\rightarrow j=9\rightarrow9$

$i=4\rightarrow j=4\rightarrow4$

$i=4\rightarrow j=8\rightarrow8$

$i=4\rightarrow j=12\rightarrow12$

$i=4\rightarrow j=16\rightarrow16$

برای بقیه عددها هم این ریتم هستش.حالا اگه به نحوه ی اجرا دقت کنی میبینی به ازای هر $i$ یه سری عددی داریم با جمله اول $i$ و جمله اخر $i^2$ و تعداد جملات و قدر نسبت هم $i$ هستش.خب مجموع سری حسابی رو که میدونیم چجوری به دست میاد خب حالا ما باید برای هر $i$ این مجموع رو به دست بیاریم که میشه:

$\sum^n_{i=0}\frac{(i i^2)\ast i}{2}=\sum\frac{i^2}{2} \sum\frac{i^3}{2}=\theta(n^4)$

بفرمایید

ممنون از اینکه اینقدر خوب راه حل را نوشتید. کاملا درست هست .