تالار گفتمان مانشت

سوال رو پیوست کردم، جواب گزینه 3 هست،چرا؟
پوران گفته که دو تا حلقه داخلی مرتبه‌شون میشه n، چرا؟

[attachment=16984]

دوحلقه داخلی بهم وابسته اند. در 1=j حلقه داخلی تر یکبار اجرا میشه. در 2=j دستور دوبار اجرا میشه و در 4=j هم که 4 بار دستور اجرا میشه و الی آخر. فرض میکنیم n توانی از دو باشه و مثلا دو به توان k باشه.
1+2+4+...+(2^k) =( 2^k+1) - 1 = 2*(2^k) - 1 =2n-1

حلقه اول هم که چون هردفعه به توان دو میرسه logn میشه.درنتیجه میشه nlogn

Sent from my GT-S5660 using Tapatalk 2

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

[tex]j=1\longrightarrow1[/tex]

[tex]j=2\longrightarrow2[/tex]

[tex]j=4\longrightarrow4[/tex]

[tex]j=8\longrightarrow8[/tex]

و همینطوری ادامه بده.حال قبول داری [tex]j[/tex] داره به صورت [tex]2^p[/tex] تغییر میکنه.p از صفر شروع میشه.حالا این اجرا تا چه وقتی
ادامه پیدا میکنه؟
تا وقتی که [tex]2^p<n[/tex] درسته؟یعنی وقتی که [tex]2^{p 1}>n[/tex] دیگه حلقه اجرا نمیشه.درسته؟
پس ما میتونیم یه تقریب بزنیم به این صورت که:[tex]2^{p}\cong n[/tex] درست؟
حالا مجموع زمان اجراها رو محاسبه میکنیم:
[tex]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)[/tex]

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

(22 مهر 1393 11:24 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببین زمان اجرای حلقه دوم و سوم [tex]\lg(n)[/tex] نمیشه چون به ازای هر [tex]j[/tex] توی حلقه دوم مقدار [tex]k[/tex] توی حلقه سوم فرق داره درسته؟
یعنی وقتی [tex]j[/tex] مقدارش ۱ باشه حلقه سوم ۱ بار اجرا میشه و وقتی [tex]j=2[/tex] باشه حلقه سوم ۲ بار اجرا میشه و وقتی [tex]j=4[/tex] باشه حلقه سوم ۴ بار اجرا میشه پس لگاریتمی تغییر نمیکنه.
حالا این تریس رو داشته باش:

[tex]j=1\longrightarrow1[/tex]

[tex]j=2\longrightarrow2[/tex]

[tex]j=4\longrightarrow4[/tex]

[tex]j=8\longrightarrow8[/tex]

و همینطوری ادامه بده.حال قبول داری [tex]j[/tex] داره به صورت [tex]2^p[/tex] تغییر میکنه.p از صفر شروع میشه.حالا این اجرا تا چه وقتی
ادامه پیدا میکنه؟
تا وقتی که [tex]2^p<n[/tex] درسته؟یعنی وقتی که [tex]2^{p 1}>n[/tex] دیگه حلقه اجرا نمیشه.درسته؟
پس ما میتونیم یه تقریب بزنیم به این صورت که:[tex]2^{p}\cong n[/tex] درست؟
حالا مجموع زمان اجراها رو محاسبه میکنیم:
[tex]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)[/tex]

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

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

(23 مهر 1393 04:06 ب.ظ)Ametrine نوشته شده توسط: [ -> ]

(22 مهر 1393 11:24 ب.ظ)miladcr7 نوشته شده توسط: [ -> ]ببین زمان اجرای حلقه دوم و سوم [tex]\lg(n)[/tex] نمیشه چون به ازای هر [tex]j[/tex] توی حلقه دوم مقدار [tex]k[/tex] توی حلقه سوم فرق داره درسته؟
یعنی وقتی [tex]j[/tex] مقدارش ۱ باشه حلقه سوم ۱ بار اجرا میشه و وقتی [tex]j=2[/tex] باشه حلقه سوم ۲ بار اجرا میشه و وقتی [tex]j=4[/tex] باشه حلقه سوم ۴ بار اجرا میشه پس لگاریتمی تغییر نمیکنه.
حالا این تریس رو داشته باش:

[tex]j=1\longrightarrow1[/tex]

[tex]j=2\longrightarrow2[/tex]

[tex]j=4\longrightarrow4[/tex]

[tex]j=8\longrightarrow8[/tex]

و همینطوری ادامه بده.حال قبول داری [tex]j[/tex] داره به صورت [tex]2^p[/tex] تغییر میکنه.p از صفر شروع میشه.حالا این اجرا تا چه وقتی
ادامه پیدا میکنه؟
تا وقتی که [tex]2^p<n[/tex] درسته؟یعنی وقتی که [tex]2^{p 1}>n[/tex] دیگه حلقه اجرا نمیشه.درسته؟
پس ما میتونیم یه تقریب بزنیم به این صورت که:[tex]2^{p}\cong n[/tex] درست؟
حالا مجموع زمان اجراها رو محاسبه میکنیم:
[tex]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)[/tex]

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

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

اگه قسمتی مثل اون دو به توان p منظورتونه که اونه مشابهش توی جزوه ی استاد یوسفی هم هستش ولی اگه کل سوال رو میگید نه تحلیل خودمه