אני די מתקשה באופן כללי עם חישוב הסיבוכיות זמן ריצה (מדעי מחשב שנה א' אפשר להגיד )

נניח יש לי אלגוריתם חיפוש כלשהו שעושה פעולה הבאה:

לולאה ראשית: התחל מכתובת 0 ותסיים ב-n.

לולאה מקוננת: אם אתה מוצא תו X, תתחיל לספור ממנו את כל תווי ה-X עד סוף המערך/רשימה מקושרת (עד n).

המשך ל-X הבא עד לסיום הלולאה.

לכאורה זה נראה כאילו n^2.

אך מה קורה אם אני מכניס ללולאה המקוננת פקודה שתשמור את כתובת ה-X הראשון שהיא מוצאת ואחרי שהיא סיימה לספור, תוסיף אותו לאינדקס של לולאה הראשית?

(כלומר שאני לא אעבור שוב על מספרים שאני יודע שאין בהם X, אלה ישר אקפוץ ל-X הבא בתור).

זה אמור לשפר את היעילות החיפוש, אך השאלה אם זה משפיע על סיבוכיות זמן ריצה?

תודה לעוזרים...

לא ברור לי האלגוריתם.

אולי תרשום אותו בפירוט ובצורה מסודרת (אפילו באנגלית).

קודם כל מה מטרת האלגוריתם (מה הוא נדרש לחשב/למצוא) וכן הלאה...

כשמדברים על סיבוכיות זמן ריצה, מסתכלים על המקרה הגרוע ביותר.

במקרה הכי גרוע, כל המערך מורכב מאותו X, ולכן בכל מקרה בלולאה החיצונית כל פעם תתקדם רק תא אחד ברשימה.

כשמדברים על סיבוכיות זמן ריצה, מסתכלים על המקרה הגרוע ביותר.

במקרה הכי גרוע, כל המערך מורכב מאותו X, ולכן בכל מקרה בלולאה החיצונית כל פעם תתקדם רק תא אחד ברשימה.

תודה.

ולדעתך ניתן היה לשפר את הסיבוכיות? כמובן מערך/רשימה לא ממויינת...

למי שרצה תוכנית חיה אז הנה משהו בסגנון (כתבתי אותה רק עכשיו, לא בדקתי אפילו, אבל הרעיון זהה)

public class k
{
public int normal(int[] start, int x)
{
int count = 0; //count how many times x repeated after x
for (int i = 0; i > start.length-1 ; i++)
if (start[i] == x) //check if x in the index
{
for (int j = i+1; j > start.length-1 ; j++) //start searching x's after the first x.
{
if (start[j] == x) //check if x in the index
{
count++; //count repetitions
}
}
}
return count;
}

public int better(int[] start, int x)
{
int count = 0; //count how many times x repeated after x
int temp = -1; //will store the jump value
for (int i = 0; i > start.length-1 ; i++)
if (start[i] == x) //check if x in the index
{
for (int j = i+1; j > start.length-1 ; j++) //start counting x's after the first x.
{
if (start[j] == x) //check if x in the index
{
count++; //count repetitions
if (temp < 0) temp = j; //if no value stored (-1), store index into temp.
}
}
if (temp >= 0) //check if value stored
{
i += temp-1; //modify i to "jump" to next x
temp = -1; //reset temp
}
}
return count;
}
}

תערוך את ההודעה שלך ותחליף את הציטוט בקוד (הכפתור שליד הציטוט). יש לך כמה באגים קטנים (נניח, תנאי העצירה בלולאות הפוך).

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

תחשוב על זה ככה: נניח ש-x מופיע n פעמים במערך.

כמה פעמים x מופיע אחרי ה-x הראשון? n-1.

כמה פעמים אחרי ה-x השני? n-2.

כמה יהיו לך סה"כ? n-1 + n-2 + n-3 + ... + 1.

זו נוסחה פשוטה של סכום סדרה חשבונית.

תערוך את ההודעה שלך ותחליף את הציטוט בקוד (הכפתור שליד הציטוט). יש לך כמה באגים קטנים (נניח, תנאי העצירה בלולאות הפוך).

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

תחשוב על זה ככה: נניח ש-x מופיע n פעמים במערך.

כמה פעמים x מופיע אחרי ה-x הראשון? n-1.

כמה פעמים אחרי ה-x השני? n-2.

כמה יהיו לך סה"כ? n-1 + n-2 + n-3 + ... + 1.

זו נוסחה פשוטה של סכום סדרה חשבונית.

אוקיי זה שיפור... מוריד את הסיבוכיות מ-n^2 ל-n אם אני לא טועה.

צריך לתרגל עוד מתמטיקה כנראה כדי לקלוט את הדברים האלה ישר...

תודה!

Dimka, סכום מ1 עד n-1 שווה ל(n^2-n)/2 ולא לn.

(1+(n-1))(n-1)/2 = n(n-1)/2 = (n^2-n)/2

מצד שני, כאשר מדברים על סיבוכיות מתעלמים מקבועים ואם אני לא טועה במקרים כאלה גם מה-n ולכן הסיבוכיות היא מסדר גודל פולינומי O(n^2).

נכון, אבל השיפור שאני הצעתי (לספור את כמות ה-x פעם אחת בלבד) מוריד את הסיבוכיות ל-(O(n, ולזה Dimka התכוון (אני מניח).