חישוב סיבוכיות זמן - למה אלו התשובות?

[roma4k]

היי צהריים טובים.

אני לא מבין כל כך איך מחשבים את סיבוכיות הזמן בשני הקודים הבאים, אשמח אם תוכלו לעזור.

void f3(int n)
{
int i, m=1;
for(i = 0; i < n; i++)
m *= n;
while( m > 6)
m /= 3;
}

הסיבוכיות היא n*logn

int f4(int n)
{
int i, j, k=1, count;
for(i = 0; i < n; i++) {
k *= 3;
for(j = k; j; j /= 2)
count++;
}
return count;
}

הסיבוכיות היא n^2

תודה רבה מראש.

[שניצל]

ב-f3 יש שתי לולאות:

הלולאה הראשונה היא לולאה באורך n בדיוק, ולכן הסיבוכיות היא n. בסופה אתה נותר עם !m=n (כלומר n עצרת). מבחינת סדרי גודל של סיבוכיות, זה כמו n בחזקת n.

הלולאה השנייה תרוץ בערך (log3(m איטרציות, כלומר סיבוכיות של (log3(n^n שזה (nlog3(n, שזה כמובן nlogn.

השני דווקא יוצא לי גם כן nlogn ולא n^2...

[roma4k]

תודה על התתייחסות.

מה שאני לא מבין זה מדוע בלולאה השניה זה log3(m)? האם ברגע שיש חלוקה זה סיבוכיות לוגריתמית?

התרגיל השני הוא n^2, בדקתי שוב פעם.

[QttP]

בתרגיל הראשון M הוא לא N!, אלא באמת N^N, שכן מכפילים ב-N בכל פעם... N! ו-N^N היא ממש לא אותה סיבוכיות, ולהוכיח ש-logn! = o(logn^n) הוא תרגיל לא כל-כך טריוויאלי.

מה שכן, זה באמת n*log_3(n)= nlogn.

למה? תחשוב שאתה מתחיל ממספר N ומחלק אותו ב-3 כל פעם? אחרי כמה צעדים תגיע ל-1? נכון, אחרי בערך log בבסיס 3 של N. כי תחשוב שהיית מתחיל מ-1 ומכפיל ב-3 כל פעם. אחרי X צעדים היית מגיע ל-3 בחזקת X. נסמן N = 3^X ונקבל שמספר הצעדים הוא log בבסיס 3 של N.

לגבי השאלה השניה: יש שם לולאה בתוך לולאה.

החיצונית רצה N פעמים.

הפנימית רצה logK פעמים (על-פי אותו טיעון כמו בשאלה 1).

בכל איטרציה של הלולאה הפנימית K=3^I.

לכן סה"כ זמן הריצה הוא

סכום (I מ-1 עד N) של log3^i , כלומר סכום (I מ-1 עד N) של O(i), כלומר N^2.

[שניצל]

צודקים, הייתה לי טעות, בשני המקרים לא שמתי לב במה כופלים

[roma4k]

תודה רבה על העזרה לשניכם.

אני עדיין לא כל כך מבין את הקוד השני.

הלולאה הפנימית בקוד השני היא:

for(j = k; j; j /= 2)
count++;

מתי היא למעשה תעצור? הריי J אף פעם לא יהיה 0..

לא הבנתי גם איך עשית את השורה האחרונה בתשובתך.

[שניצל]

היא תעצור כי j הוא מטיפוס int, ולא double. חילוק ב-2 גם מעגל את התוצאה כלפי מטה.

[roma4k]

thanks, you all helped me a lot.