פורסם 2010 במאי 2915 שנים אני עוד חדש בכל הקטע של הסיבוכיות ( וחדש בפורום ) ואשמח לעזרה עם 2 קודים קצרים ... הראשון : int a = 3 ;while ( a<=n) a=a*a;השני:public void foo ( int m , int n ){int i = m;while ( i > 100 ) i = i/3;for ( int k=i; k>=0; k-- ){ for ( int j = 1 ; j<n ; j*=2 ) System.out.println(k+i); system.out.println();}}מהסתכלות קצרה בקוד אני חושב שהסיבוכיות של הראשון היא לוג אן , ושל השני :logM + m*logNאין לי מושג אם זה נכון - וגם אם כן , אני לא כל כך יודע להסביר...עזרה מישהו ?
פורסם 2010 במאי 2915 שנים לפני שיהיה אפשר להסתכל על הקוד שלך, בבקשה שים אותו בתוך תגית Code,אחרת זה לא קריא בכלל... (מופיע בתור כפתור סולמית - # - בעת כתיבה הודעה)
פורסם 2010 במאי 2915 שנים לגבי הראשון:תחשוב על זה ש-a הוא תמיד 3 בחזקת i כלשהו, ואז תחשוב על קצב הגדילה של i.לגבי השני:שים לב ש-k לא באמת תלוי ב-m ההתחלתי באופן ישיר.
פורסם 2010 במאי 2915 שנים אני אגיד לך בערך אני כבר לא זוכר הכי טוב אבל כל מספר זו איטרציה1: a*a= a^22: a^2 * a^2 = a^4........k: ... a^2^kעכשיו אתה רוצה לדעת מתיa<nוזה יקרה כאשר (בערך..)a=a^2^k =nאתה מוציא לוג פעמיים ומוצא את הk שזו הסיבוכיות שלך O(loglog(n((הלולאה הראשונה מתבצעת O(logm( פעמים בזה צדקתאבל הלולאה השניה מתבצעת O(logn) פעמים כפול קבוע כלשהו קטן שווה ל100 שלא צריך להתייחס אליו..זאת מכיוון שעד שאתה מגיע ללולאה השניה הערך k הוא לכל היותר 100 (שים לב לתנאי העצירה של הלולאה הראשונה).מקווה שהסברתי טוב מספיקנ.ב.חבל שאין פה תמיכה ב mathtype!!!!!
פורסם 2010 במאי 3015 שנים מחבר אני ממש מצטער - אבל עדיין לא הצלחתי להבין כל כך .... שתי התגובות שיקבלתי נראות כמו 2 גישות שונות - ואף אחת מהן לא הבנתי עד הסוף .... אולי הבעיה שלי היא בדרך לגשת לבעית סיבוכיות - למרות התגובות המפורטות וההסברים , אשמח אם מישהו יוכל בבקשה לנסות להסביר לי שוב ובפירוט ...תודה מראש ! [br]פורסם בתאריך: 30.05.2010 בשעה 21:08:24קראתי עוד פעם לאט ובזהירות והבנתי קצת יותר - לגבי השאלה הראשונה , הבנתי שכמו ששניצל אמר - ניתן לחשוב על זה כ-3 בחזקת 2 כפול קבוע כלשהו... למה הקבוע הזה מייצג את הסיבוכיות ? ואיך מפה אנחנו מגיעים ללוג ? בקשר לשאלה השניה - הבנתי למה אמרתם ש-K אפשר להגדיר כמספר ולא כמשתנה ( ואז בעצם נתעלם ממנו בסיכויות ) אבל אני לא באמת יודע להסביר למה הלולאה השנייה היא LOG ... חוץ מזה שאינטואיטיבית אני רואה חילוק/כפל אני זורק לוג - אני לא באמת יודע להסביר מתי נשתמש בזה ואיך בצורה נכונה...אני חושב שמיקדתי קצת יותר את השאלה שלי
פורסם 2010 במאי 3015 שנים לגבי השאלה הראשונה , הבנתי שכמו ששניצל אמר - ניתן לחשוב על זה כ-3 בחזקת 2 כפול קבוע כלשהו... למה הקבוע הזה מייצג את הסיבוכיות ? ואיך מפה אנחנו מגיעים ללוג ? למה 3 בחזקת 2 כפול קבוע כלשהו, ולא 3 בחזקת 2 בחזקת קבוע כלשהו?אבל אני לא באמת יודע להסביר למה הלולאה השנייה היא LOG ... חוץ מזה שאינטואיטיבית אני רואה חילוק/כפל אני זורק לוג - אני לא באמת יודע להסביר מתי נשתמש בזה ואיך בצורה נכונה...הרעיון הוא כזה: אתה רוצה למצוא נוסחה כללית ל-j, לפי האיטרציה - כלומר, משהו כמו "באיטרציה ה-i ערכו של j יהיה 2 בחזקת i". לפי הנוסחה הזו, תוכל לומר באיזו איטרציה יתקיים j >= n.
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.