תרגיל ב-c#, שיפור יעילות הפעולה בסדר גודל.

[lesForce]

שלום לכולם. קיבלנו שאלה שאני לא מצליח לפתור כל כך.

נתונה מטריצה mat מסוג INT שמספריה כבר ממוינים. ז"א בכל שורה ובכל עמודה המספרים ממוינים בסדר עולה - מהקטן לגדול. בכל שורה בנפרד ובכל עמודה בנפרד אין מספר שמופיע יותר מפעם אחת. הפעולה מחזירה את מספר הפעמים שהמספר X מופיע במטריצה.

הפעולה הולכת ככה:

public static int matrizh (int [] [] mat ,int x)
int count =0;
for (int i=0; i<mat.length ; i++)
for (int j=0;j<mat.length ; j++)
if (mat[i] [j] ==x 
counter ++;
return counter;

עכשיו השאלה היא :

הצע דרך לשיפור יעילות הפעולה בסדר גודל . אין צורך לכתוב אלא רק להציע.

יש למישהו רעיון?

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

תודה לכולם!

[geniaXP]

אתה אמור לרשום mat.GetLength(X) כאשר אם X זה 0 אז זה שורות ואם X זה 1 אז עמודות.

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

[שניצל]

geniaXP - מה שאמרת נכון אם זה מערך דו-מימדי, כלומר [,]int. במקרה הנתון זה מערך של מערכים.

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

קודם כל, תחשוב מה הסיבוכיות של המימוש הנוכחי, כדי שיהיה לך למה להשוות.

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

ולגבי השאלה הנוספת: המטריצה הזו פשוט מערך של מערכים - אין לה מושג של שורות ושל עמודות (זה כבר עניין של תצוגה, ואם אתה מדפיס מטריצה כזו אז אפשר גם ככה וגם ככה). mat.length זה פשוט האורך של המערך הזה. כל איבר ב-mat הוא מערך בפני עצמו, ויש לו אורך משלו. בעקרון, הלולאה של j הייתה צריכה להיות משהו כזה:

for (int j = 0 ; j < mat[i].length ; j++)

כי ייתכן שהמטריצה לא מלבנית.

[lesForce]

האמת שבשאלה היה רשום מטריצה ריבועית ומשום מה השמטתי את הפרט הזה.

עדיין לא הבנתי ממש את הlentgh פה...

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

וכשהם אומרים סדר גודל אז הם מתכוונים כיאלו שבמקום שזה יהיה O(n^2)

זה יהיה משהו יותר קטן. לא קשור כמה n גדול . ולכן גם אם תעשה לולאת while שתעצר באמצע ולא תעבור על כל המערך זה לא ישפר את סדר הגודל , נכון?

[שניצל]

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

כלומר, היא מערך של אובייקטים שכל אחד מהם הוא מערך של int. ה-length שך mat הוא פשוט האורך של המערך הראשי. אם אתה רוצה את האורך של אחד מתתי המערכים אז אתה צריך לגשת ל-mat[i ].length.

לגבי סדר הגודל - בדיוק.

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

[lesForce]

מה זאת אומרת מערך של מערכים.מה זה אובייקטים בכלל?

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

אולי אתה מתכוון שכיאלו הם היכנסו 2 מערכים פשוטים נפרדים של קשורים אחד לשני?

[שניצל]

לא 2 מערכים.

נניח שהמטריצה שלך היא בגודל n על n. זה אומר ש-mat הוא n מערכים, שכל אחד מהם הוא מערך בגודל n.

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

אבל אם לא למדת על אובייקטים, אז עדיף שלא להתעמק בזה עדיין.

[lesForce]

אם לדוגמא יש לי מטריצה כזו:

12 10 8 4

23 20 12 9

25 24 11 10

אז מה הlentgh שלה?

[שניצל]

שוב, זה עניין שרירותי - אתה יכול להחליט שהאינדקס הראשון הוא השורות והשני הוא העמודות (ואז זו מטריצה שמימדיה הם 3 על 4, כלומר mat.length == 3), ואתה יכול להחליט שהאינדקס השני הוא השורות והראשון הוא העמודות (ואז זו מטריצה שמימדיה הם 4 על 3, כלומר mat.length == 4).

[lesForce]

ואי אני לא ממש מבין את זה...

האמת שהשאלה עוד ממשיכה, הם נותנים עוד פעולה:

    public static int cout2(int[][] mat, int x)
    {
      int counter = 0;
      int n = mat.Length;
      for (int i = 0; i < mat.Length; i++)
      {
        for (int j = 0; j < n; j++)
          if (mat[i][j] == x)
            counter++;
        n = j - 1;
      }
      return counter;
    }

ואז יש שאלה

האם השינוי שערכנו באלגוריתם COUT2 גרר ייעול האלגוריתם? נמק והוכח. בתשובתך התייחס למקרה הכולל וכן למקרים פרטניים.

בתכלס אם אתה מבצע נוסחה של ייעלות יבשה

בCOUT1 זה יוצא

3n^2+3n+3

ובcout2

3n^2+4n+4

ואפילו אם תיקח n קטן (אפילו 1) תמיד cout1 יהיה יותר יעיל , כל שכן בn גדול.

אבל אני בכלל לא מבין איך לרוץ על הפעולה הזאת.. אתה יכול אולי לתת לי דוגמא קצרה של מערך\ים שאיתו אני אנסה לרוץ על הפעולה...?

[שניצל]

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

[Jaman]

exzt

האם למדתם רקורסיה וחיפוש בינארי?

אם כן תחשוב איך זה יכול להשתלב בבעיה שלך.

[geniaXP]

geniaXP - מה שאמרת נכון אם זה מערך דו-מימדי, כלומר [,]int. במקרה הנתון זה מערך של מערכים.

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

קודם כל, תחשוב מה הסיבוכיות של המימוש הנוכחי, כדי שיהיה לך למה להשוות.

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

אז אפשר לעשות חיפוש בינארי

[שניצל]

נכון, וזה הייעול שאני מציע.

בעקרון אפשר לעשות חיפוש בינארי על כל שורה בנפרד, ואז לשפר מסיבוכיות של n^2 ל-nlogn.

אבל אני מניח שהם מחפשים משהו יותר חכם מזה (אפשר לעשות איזה חיפוש בינארי משולב על השורות והעמודות או משהו כזה).

[Yehudaa]

שניצל בקורס המבוא שלי שיפור מ N^2 ל NLOGN נחשב שיפור בסדר גודל .

ואם אני לא טועה אי אפשר לפתור את זה בפחות מזה כי המטריצה הזאת לא ממוינת .