What is the time complexity T(n) of the nested loops below? For simplicity, you may assume that n is a power of 2. That is, n = 2k for some positive integer k.
کد:
[align=left] i = n;
while (i >= 1){
j = i;
while (j <= n){
< body of the while loop> //Needs Θ (۱).
j = 2 * j;
}
i =[i/2];
}
[/align]تعداد تکرارش تقریباً میشه [tex]\log^3n[/tex] حالا چون توان ۳ داره نمیدونم جزء همون [tex]\theta(\log n)[/tex] هست یا نه.
چون اون مقادیری هم که باهم جمع میشن [tex]\frac{\log n(\log n 1)}{2}[/tex] رو میسازه و حلقه بیرونی هم [tex]\log n[/tex] میشه.
فرض کنید مقدار n=1024 باشه. تکرار حلقه i که مشخصه ۱۰ باره که همون [tex]\log n[/tex] هست. حلقه j هم به ترتیب ۱ تا ۱۰ بار به ازای مقادیر i تکرار میشه. یعنی j مقادیر ۱۰۲۴ و ۵۱۲ و ۲۵۶ و ۱۲۸ و ... و ۱ رو میگیره. تعداد تکرارش میشه ۵۵ بار که همون [tex]\frac{\log n(\log n 1)}{2}[/tex] میشه. چندتا عدد ثابت هم داره که تاثیری نداره و میشه گفت فقط باید پیچیدگی [tex]\log^3n[/tex] رو حساب کرد. البته مبنای همه لگاریتمها ۲ هست.
(۲۲ فروردین ۱۳۹۱ ۰۸:۴۴ ب.ظ)Lakikharin نوشته شده توسط: تعداد تکرارش تقریباً میشه [tex]\log^3n[/tex] حالا چون توان ۳ داره نمیدونم جزء همون [tex]\theta(\log n)[/tex] هست یا نه.۱/ فرض کنیم n=8 ، حلقه خارجی میشه ۳ ، اما در حلقه داخلی تکرار j میشه ،۱+۲+۳+۴=۱۰ ،
چون اون مقادیری هم که باهم جمع میشن [tex]\frac{\log n(\log n 1)}{2}[/tex] رو میسازه و حلقه بیرونی هم [tex]\log n[/tex] میشه.
فرض کنید مقدار n=1024 باشه. تکرار حلقه i که مشخصه ۱۰ باره که همون [tex]\log n[/tex] هست. حلقه j هم به ترتیب ۱ تا ۱۰ بار به ازای مقادیر i تکرار میشه. یعنی j مقادیر ۱۰۲۴ و ۵۱۲ و ۲۵۶ و ۱۲۸ و ... و ۱ رو میگیره. تعداد تکرارش میشه ۵۵ بار که همون [tex]\frac{\log n(\log n 1)}{2}[/tex] میشه. چندتا عدد ثابت هم داره که تاثیری نداره و میشه گفت فقط باید پیچیدگی [tex]\log^3n[/tex] رو حساب کرد. البته مبنای همه لگاریتمها ۲ هست.
برای n>=j=8 یکبار ، ۴=n>=j دوبار ۲=n>=j سه بار و ۱=n>=j چهار بار j تکرار میشه
[tex]{\log n(\log n 1)}/{2}=log8(log8 1)/2=3(3 1)/2=6[/tex]
در صورتی که مقدارش ۱۰ میشه .
یا واسه عدد n=16 حساب کن میشه ۱۵ بار در معادله فوق صدق نمی کنه باید یه تغییری در معادلتون ایجاد کرد
فکر کنم معادله به صورت زیر باید تغییر کنه نظرت چیه ؟
[tex](logn 1)(logn 2)/2[/tex]
۲/ پیچیدگی [tex]log^{3}n[/tex] فکر کنم میشه خودش نیاز به محاسبه نداره .
برای بدست آوردن پیچیدگی، عدد دقیق نیاز نیست. عدد ثابت تاثیر اونچنانی توی پیچیدگی نداره. اصل شمارش نیست که مقدار دقیق بخاد. فقط یه مرتبست. برای همین پیچیدگی n رو با ۱۰n برابر میگیریم.
(۲۲ فروردین ۱۳۹۱ ۱۰:۲۱ ب.ظ)Lakikharin نوشته شده توسط: برای بدست آوردن پیچیدگی، عدد دقیق نیاز نیست. عدد ثابت تاثیر اونچنانی توی پیچیدگی نداره. اصل شمارش نیست که مقدار دقیق بخاد. فقط یه مرتبست. برای همین پیچیدگی n رو با ۱۰n برابر میگیریم.البته فقط خواستم دقیق به دست بیاد .
ضمنا با اینکه دانشجوی کارشناسی هستید اما سواد علمی بالایی دارید جدا تبریک میگم .
امیدوارم در تمام مدارج علمی موفق باشید .
البته یه ابهام دارم من .
فکر کنم [tex]logn[/tex] حلقه خارجی رو نباید در [tex]log^{2}n[/tex] حلقه داخلی ضرب کرد ، باید جمع کرد .
جواب کلی :
[tex]([(logn 1)(logn 2)]/2) (logn 1) \Rightarrow T(n)=\Theta (log^{2}n)[/tex]
تا نظر دوستان چی باشه ؟
درسته. نمیدونم چجوری یه لوگاریتم اضافی ضرب کردم. فقط ۲تا حلقه داره. برای اون مثال عددی مقادیر حلقه بیرونی هم لحاظ شده. پیچیدگیش همون log^2n میشه.