سوال رو پیوست کردم، جواب گزینه ۳ هست،چرا؟
پوران گفته که دو تا حلقه داخلی مرتبهشون میشه n، چرا؟
[attachment=16984]
دوحلقه داخلی بهم وابسته اند. در ۱=j حلقه داخلی تر یکبار اجرا میشه. در ۲=j دستور دوبار اجرا میشه و در ۴=j هم که ۴ بار دستور اجرا میشه و الی آخر. فرض میکنیم n توانی از دو باشه و مثلا دو به توان k باشه.
۱+۲+۴+...+(۲^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]
(۲۲ مهر ۱۳۹۳ ۱۱:۲۴ ب.ظ)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]
آخه من تو دو، سه تا کتاب نگاه کردم همه یه خط نوشته بودن فقط.
(۲۳ مهر ۱۳۹۳ ۰۴:۰۶ ب.ظ)Ametrine نوشته شده توسط:اگه قسمتی مثل اون دو به توان p منظورتونه که اونه مشابهش توی جزوه ی استاد یوسفی هم هستش ولی اگه کل سوال رو میگید نه تحلیل خودمه(22 مهر ۱۳۹۳ ۱۱:۲۴ ب.ظ)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]
آخه من تو دو، سه تا کتاب نگاه کردم همه یه خط نوشته بودن فقط.