خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]
حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]
و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]
(۲۹ مرداد ۱۳۹۳ ۰۸:۱۹ ب.ظ)miladcr7 نوشته شده توسط: خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]
حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]
و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]
جواب این طوری هست:
[tex]\frac{n}{logn}[/tex] <--- سطر اول درخت
[tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] <---سطر دوم درخت
[tex]\frac{\frac{n}{5^2}}{\log(\frac{n}{5^2})}[/tex] سطر دوم درخت که ۴ تا از اینا هست
حالا میرسیم به نوشتم فرمولهای هر سطر :
نکتش اینه که [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}=\frac{n}{(\log n - \log5)}=\frac{n}{\log n-1}[/tex]
توجه کنید که لگاریتم در مبنای ۵ هست به خاطر همینه که لگاریتم ۵ برابر یک میشه
همونطور که میبینید دقیقا فرمولش با اون مثالی که توی کتاب حلش کرده برابره و جوابشون یکی میشه
(۲۹ مرداد ۱۳۹۳ ۰۹:۵۱ ب.ظ)shayesteb نوشته شده توسط:(29 مرداد ۱۳۹۳ ۰۸:۱۹ ب.ظ)miladcr7 نوشته شده توسط: خب ببین یه راست بریم تا وقتی که مجموع رو حساب کنیم.مجموع به صورت یه کسره درسته؟وقتی مقدار هر سطح رو حساب کنیم صورت کسر همیشه [tex]n[/tex] میشه که تو این مشکل نیست خب ؟
حالا میمونه مخرج:توی سطح اول مخرج همه ی کسرها اینه:[tex]\log^{\frac{n}{2}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{2}}_2[/tex]: kjk[tex]\log^{\frac{n}{2}}_2=\log^n_2-\log^2_2=\log^n_2-1[/tex]
حالا توی سطح دوم مخرج همه کسر ها اینه:[tex]\log^{\frac{n}{4}}_2[/tex] حالا مقدار اینو چجوری محاسبه میکنیم؟
[tex]\log^{\frac{n}{4}}_2=\log^n_2-\log^4_2=\log^n_2-2[/tex]
و برای بقیه سطح ها هم ادامه داره و نهایتا مجموع:
[tex]n(\frac{1}{\lg n} \frac{1}{\lg n-1} \frac{1}{\lg n-2} ... 1)=\theta(n.\lg\lg n)[/tex]
جواب این طوری هست:
[tex]\frac{n}{logn}[/tex] <--- سطر اول درخت
[tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}[/tex] <---سطر دوم درخت
[tex]\frac{\frac{n}{5^2}}{\log(\frac{n}{5^2})}[/tex] سطر دوم درخت که ۴ تا از اینا هست
حالا میرسیم به نوشتم فرمولهای هر سطر :
نکتش اینه که [tex]\frac{\frac{n}{5}}{\log(\frac{n}{5})}=\frac{n}{(\log n - \log5)}=\frac{n}{\log n-1}[/tex]
توجه کنید که لگاریتم در مبنای ۵ هست به خاطر همینه که لگاریتم ۵ برابر یک میشه
همونطور که میبینید دقیقا فرمولش با اون مثالی که توی کتاب حلش کرده برابره و جوابشون یکی میشه
نه اشتباه نکنید لگاریتم در مبنای ۲ نیست در مبنای ۵ هست. چرا؟
چونکه در صورت سوال داریم [tex]T(\frac{n}{5})[/tex] پس در هر سطر (همونطور که در بالا میبینید) توانی از ۵/n جایگزین n میشود.
خب صورت اصلی که اینه:[tex]T(n)=5T(\frac{n}{5}) \frac{n}{\lg n}[/tex]
خب پایه لگاریتم دو هستش و ما هر بار داریم به جای n مقدار میذاریم ،پایه که تغییر نمیکنه.توی مثال صفحه ۴۲ هم اینطور بود بازم همون پایه لگاریتم ۲ بود.
ولی فرقش این بود که هر بار [tex]\frac{n}{2}[/tex] یا [tex]\frac{n}{4}[/tex] یا .... میشد که اینا توان دو هستن
مثلا:
[tex]\lg^{\frac{n}{8}}_2=\lg^n_2-\lg^8_2=\lg^n_2-3[/tex]
حالا این مثال هم اینطوره دیگه:
مثلا توی سطح دوم داریم:
[tex]\lg^{\frac{n}{25}}_2=\lg^n_2-\lg^{25}_2=\lg^n_2-2\lg^5_2[/tex]
اشتباه میگم؟
سلام. بچه ها تو کتاب مقسمی یه چیزی بیان شده که برا من عجیبه! به این صورت که اگر k=0 باشه، جواب این عبارت صفر میشه:
a[i] = k++
ینی:
a[i] = 0
و این برخلاف چیزیه که من تا حالا میدونستم. آیا من درست متوجه موضوع نشدم یا توضیح مقسمی مشکل داره؟ در ضمن این مربوط به سوال ۱۵ صفحه ۲۸ کتابشه.
(۰۲ مهر ۱۳۹۳ ۰۸:۰۷ ب.ظ)ldns0098 نوشته شده توسط: سلام. بچه ها تو کتاب مقسمی یه چیزی بیان شده که برا من عجیبه! به این صورت که اگر k=0 باشه، جواب این عبارت صفر میشه:
a[i] = k++
ینی:
a[i] = 0
و این برخلاف چیزیه که من تا حالا میدونستم. آیا من درست متوجه موضوع نشدم یا توضیح مقسمی مشکل داره؟ در ضمن این مربوط به سوال ۱۵ صفحه ۲۸ کتابشه.
سلام، ببینید عبارات ++k و k++ با هم فرق دارن، در عبارتی که شما گفتید چون شکل اولی رو گذاشته یعنی اول محتوای k رو بریز تو a ،بعد یکی به k اضافه کن. اما اگه شکل دوم یعنی k++ به کار رفته بود ،یعنی اول یکی به k اضافه کن بعد بریزش تو a .
سلام خواستم بدونم سوالات مربوط به لیستای پیوندی چطور حل میشن
مثل این سوال
![[تصویر: 391184_bdrf2rdhzq8ng53h9mh1.jpg]](https://img.manesht.ir/391184_bdrf2rdhzq8ng53h9mh1.jpg)