(۲۲ مهر ۱۳۹۳ ۱۱:۲۴ ب.ظ)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 نوشته شده توسط:  

(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]

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