נתונות המחלקות הבאות:

public interface A{
   public int what (int [] data);

}

public class B implements A
{

public int what(int[] data)
{       
  int h1 = 0;
  int h2 = 1;

  for (int i = 0; i < data.length; i++)
  {
       int v = data[i];
       int c = 1;

       for (int j = i+1; j < data.length; j++)
       {
            if (data[j] == v)
                    c++;
       }

       if (c > h2)
       {
            h2 = c;
            h1 = v;
       }
  }
  return h1;
}

}

1. הסבירו מה מבצעת השיטה באופן כללי --> מחפשת איברים זהים במערך

2. מהו סדר הגודל של זמן הריצה של השיטה ? הסבירו --> On², בגלל שעל כל איבר במערך אנחנו עוברים שוב על המערך

3. כתבו מחלקה נוספת C המממשת את A. במחלקה זו, כתבו את השיטה what כך שתפתור את הבעיה בסיבוכיות זמן ריצה קטנה מסיבוכיות הזמן של השיטה שבמחלקה B (קטנה בסדר גודל ולא רק בקבוע). כתבו שיטה יעילה ככל האפשר במונחים של זמן ריצה ושל שימוש בזיכרון.

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

שיטה שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה לא תקבל את מלוא הנקודות --> בהנחה שאני משתמש בחיפוש בינארי שהסיבוכיות שלו היא logN האם זה שיפר את הסיבוכיות ?

כתבו מחלקה נוספת C המממשת את A. במחלקה זו, כתבו את השיטה what כך שתפתור את הבעיה בסיבוכיות זמן ריצה קטנה מסיבוכיות הזמן של השיטה שבמחלקה B (קטנה בסדר גודל ולא רק בקבוע). כתבו שיטה יעילה ככל האפשר במונחים של זמן ריצה ושל שימוש בזיכרון.

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

שיטה שתהיה בסיבוכיות גדולה יותר מזו הנדרשת לפתרון הבעיה לא תקבל את מלוא הנקודות.

4. איזו שיטת מיון כדאי שהשיטה sort תממש על מנת לשפר את זמן הריצה הממוצע? מה יהיה זמן הריצה הממוצע של השיטה שכתבתם עם המיון שציינת? ומה זמן הריצה הגרוע ביותר של שיטתכם (המשתמשת במיון שציינתם)? --> האיזו שיטת מיון כדאי שהשיטה sort תממש על מנת לשפר את זמן הריצה הממוצע? מה יהיה זמן הריצה הממוצע של השיטה שכתבתם עם המיון שציינת? ומה זמן הריצה הגרוע ביותר של שיטתכם (המשתמשת במיון שציינתם)? --> הייתי בוחר במיון ערימה - Onlogn - האם צדקתי ?

לא ברור מה אתה שואל. תמקד בבקשה את השאלה שלך.

אם התשובות שלי לשאלות נכונות (מודגשות)

1. ומה היא עושה איתם?

2. נכון.

3. לא ענית על השאלה, ולא הסברת איך אתה משתמש בחיפוש בינארי.

4. סבבה, יש עוד הרבה מיונים שזו הסיבוכיות שלהם.

1. היא מחפשת איברים זהים במערך אבל מה היא עושה איתם? שים לב את איזה משתנה היא מחזירה.

2. התשובה נכונה, הפירוט קצת לוקה בחסר. יש לך כאן סכום של סדרה חשבונית.

3. למה אתה צריך חיפוש בינארי? תענה על (1) כמו שצריך ואז תבין שאתה לא צריך.

4. כל מיון של nlogn יהיה בסדר. אם יש לך הנחות על הקלט, אולי אפשר לבחור את זה היעיל יותר (לא חושב שזה ברמה שלכם עדיין)

1. הפונקציה סוכמת את האיברים הזהים ואם המספר שהתקבל גדול מ-1 מחזירה אותו - צדקתי ?

3. לא ממש הבנתי מה התשובה הנכונה

תנסה שוב. תאמר לי מה הפונקציה תחזיר עבור המערך 1,4,6,1,4,9,1,6

אני עוקב אחרי זה על דף ויצא לי שמוחזר 0

בהתחלה C=3 והוא גדול יותר מ-H2 שהוא 1 אז H2 =3 ואח"כ יצא לי C=1 והוא לא יותר גדול מ-H2

נערך 2014 בינואר 1011 שנים על-ידי gshhary

אז איך 0? הוא היה 3 ואז התנאי לא התקיים ולכן לא שינה את הערך שלו.

זה אמור לצאת 1

- - - תגובה אוחדה: - - -

הייתי שמח לתשובה לסעיף 3 היות ולא עניתי עליו נכון

זה לא שלא ענית נכון על 3, זה שלא ענית על השאלה בכלל.

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

        public static int what(int[] data)        {
            sort(data);
            int tmp = data[0];
            int num = 0;
            int count = 1;
            int totalCount = 0;


            for (int i = 1; i < data.Length; i++)
            {
                if (data[i] == tmp)
                {
                    count++;
                }
                else
                {
                    if (count > totalCount)
                    {
                        num = tmp;
                        totalCount = count;
                    }


                    tmp = data[i];
                    count = 1;
                }
            }


            if (count > totalCount)
            {
                num = tmp;
                totalCount = count;
            }


            return num;
        }

אז עכשיו אחרי שהמיון של המערך שלי הוא logN פלוס הפונקציה שרשמתי שעוברת על המערך פעם אחת שזה n אז זה יוצא nlogn

עכשיו זה בסדר ?

נערך 2014 בינואר 1011 שנים על-ידי gshhary

כן, חוץ מזה שהמיון הוא nlogn ולא סתם logn.

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

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

לא הכל זה מיונים ומערכים.