פורסם 2009 בפברואר 1616 שנים היי צהריים טובים.אני לא מבין כל כך איך מחשבים את סיבוכיות הזמן בשני הקודים הבאים, אשמח אם תוכלו לעזור.void f3(int n){int i, m=1;for(i = 0; i < n; i++)m *= n;while( m > 6)m /= 3;}הסיבוכיות היא n*lognint 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תודה רבה מראש.
פורסם 2009 בפברואר 1616 שנים ב-f3 יש שתי לולאות:הלולאה הראשונה היא לולאה באורך n בדיוק, ולכן הסיבוכיות היא n. בסופה אתה נותר עם !m=n (כלומר n עצרת). מבחינת סדרי גודל של סיבוכיות, זה כמו n בחזקת n.הלולאה השנייה תרוץ בערך (log3(m איטרציות, כלומר סיבוכיות של (log3(n^n שזה (nlog3(n, שזה כמובן nlogn.השני דווקא יוצא לי גם כן nlogn ולא n^2...
פורסם 2009 בפברואר 1616 שנים מחבר תודה על התתייחסות.מה שאני לא מבין זה מדוע בלולאה השניה זה log3(m)? האם ברגע שיש חלוקה זה סיבוכיות לוגריתמית?התרגיל השני הוא n^2, בדקתי שוב פעם.
פורסם 2009 בפברואר 1616 שנים בתרגיל הראשון 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.
פורסם 2009 בפברואר 1616 שנים מחבר תודה רבה על העזרה לשניכם.אני עדיין לא כל כך מבין את הקוד השני.הלולאה הפנימית בקוד השני היא: for(j = k; j; j /= 2)count++;מתי היא למעשה תעצור? הריי J אף פעם לא יהיה 0..לא הבנתי גם איך עשית את השורה האחרונה בתשובתך.
פורסם 2009 בפברואר 1616 שנים היא תעצור כי j הוא מטיפוס int, ולא double. חילוק ב-2 גם מעגל את התוצאה כלפי מטה.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.