אני עוד חדש בכל הקטע של הסיבוכיות ( וחדש בפורום ) ואשמח לעזרה עם 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

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

עזרה מישהו ?

לפני שיהיה אפשר להסתכל על הקוד שלך, בבקשה שים אותו בתוך תגית Code,

אחרת זה לא קריא בכלל... (מופיע בתור כפתור סולמית - # - בעת כתיבה הודעה)

לגבי הראשון:

תחשוב על זה ש-a הוא תמיד 3 בחזקת i כלשהו, ואז תחשוב על קצב הגדילה של i.

לגבי השני:

שים לב ש-k לא באמת תלוי ב-m ההתחלתי באופן ישיר.

אני אגיד לך בערך אני כבר לא זוכר הכי טוב אבל

כל מספר זו איטרציה

1: a*a= a^2

2: 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!!!!!

אני ממש מצטער - אבל עדיין לא הצלחתי להבין כל כך ....

שתי התגובות שיקבלתי נראות כמו 2 גישות שונות - ואף אחת מהן לא הבנתי עד הסוף ....

אולי הבעיה שלי היא בדרך לגשת לבעית סיבוכיות - למרות התגובות המפורטות וההסברים , אשמח אם מישהו יוכל בבקשה לנסות להסביר לי שוב ובפירוט ...

תודה מראש ! [br]פורסם בתאריך: 30.05.2010 בשעה 21:08:24

---

קראתי עוד פעם לאט ובזהירות והבנתי קצת יותר -

לגבי השאלה הראשונה , הבנתי שכמו ששניצל אמר - ניתן לחשוב על זה כ-3 בחזקת 2 כפול קבוע כלשהו... למה הקבוע הזה מייצג את הסיבוכיות ? ואיך מפה אנחנו מגיעים ללוג ?

בקשר לשאלה השניה - הבנתי למה אמרתם ש-K אפשר להגדיר כמספר ולא כמשתנה ( ואז בעצם נתעלם ממנו בסיכויות ) אבל אני לא באמת יודע להסביר למה הלולאה השנייה היא LOG ... חוץ מזה שאינטואיטיבית אני רואה חילוק/כפל אני זורק לוג - אני לא באמת יודע להסביר מתי נשתמש בזה ואיך בצורה נכונה...

אני חושב שמיקדתי קצת יותר את השאלה שלי

לגבי השאלה הראשונה , הבנתי שכמו ששניצל אמר - ניתן לחשוב על זה כ-3 בחזקת 2 כפול קבוע כלשהו... למה הקבוע הזה מייצג את הסיבוכיות ? ואיך מפה אנחנו מגיעים ללוג ?

למה 3 בחזקת 2 כפול קבוע כלשהו, ולא 3 בחזקת 2 בחזקת קבוע כלשהו?

אבל אני לא באמת יודע להסביר למה הלולאה השנייה היא LOG ... חוץ מזה שאינטואיטיבית אני רואה חילוק/כפל אני זורק לוג - אני לא באמת יודע להסביר מתי נשתמש בזה ואיך בצורה נכונה...

הרעיון הוא כזה: אתה רוצה למצוא נוסחה כללית ל-j, לפי האיטרציה - כלומר, משהו כמו "באיטרציה ה-i ערכו של j יהיה 2 בחזקת i". לפי הנוסחה הזו, תוכל לומר באיזו איטרציה יתקיים j >= n.