۰
subtitle
ارسال: #۱
یک سوال ازپیچیدگی زمانی ( T(n
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]
۰
ارسال: #۲
یک سوال از T(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]
تا نظر دوستان چی باشه ؟
فکر کنم [tex]logn[/tex] حلقه خارجی رو نباید در [tex]log^{2}n[/tex] حلقه داخلی ضرب کرد ، باید جمع کرد .
جواب کلی :
[tex]([(logn 1)(logn 2)]/2) (logn 1) \Rightarrow T(n)=\Theta (log^{2}n)[/tex]
تا نظر دوستان چی باشه ؟
۰
ارسال: #۳
یک سوال از T(n
تعداد تکرارش تقریباً میشه [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] رو حساب کرد. البته مبنای همه لگاریتمها ۲ هست.
چون اون مقادیری هم که باهم جمع میشن [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] رو حساب کرد. البته مبنای همه لگاریتمها ۲ هست.
ارسال: #۴
RE: یک سوال از T(n
(۲۲ فروردین ۱۳۹۱ ۰۸:۴۴ ب.ظ)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] فکر کنم میشه خودش نیاز به محاسبه نداره .
۰
ارسال: #۵
یک سوال از T(n
برای بدست آوردن پیچیدگی، عدد دقیق نیاز نیست. عدد ثابت تاثیر اونچنانی توی پیچیدگی نداره. اصل شمارش نیست که مقدار دقیق بخاد. فقط یه مرتبست. برای همین پیچیدگی n رو با ۱۰n برابر میگیریم.
ارسال: #۶
RE: یک سوال از T(n
(۲۲ فروردین ۱۳۹۱ ۱۰:۲۱ ب.ظ)Lakikharin نوشته شده توسط: برای بدست آوردن پیچیدگی، عدد دقیق نیاز نیست. عدد ثابت تاثیر اونچنانی توی پیچیدگی نداره. اصل شمارش نیست که مقدار دقیق بخاد. فقط یه مرتبست. برای همین پیچیدگی n رو با ۱۰n برابر میگیریم.البته فقط خواستم دقیق به دست بیاد .
ضمنا با اینکه دانشجوی کارشناسی هستید اما سواد علمی بالایی دارید جدا تبریک میگم .
امیدوارم در تمام مدارج علمی موفق باشید .
۰
ارسال: #۷
یک سوال از T(n
درسته. نمیدونم چجوری یه لوگاریتم اضافی ضرب کردم. فقط ۲تا حلقه داره. برای اون مثال عددی مقادیر حلقه بیرونی هم لحاظ شده. پیچیدگیش همون log^2n میشه.
Can I see some ID?
Feeling left out?
نگران نباش، فقط روی این لینک برای ثبت نام کلیک کن. رمزت رو فراموش کردی؟ اینجا به یادت میاریم! close