ex2.1 סיבוכיות

בתרגילי סיבוכיות תידרשו לקבוע את הסיבוכיות ברישום bigO. להגדיר מיהו הקלט n, ולהסביר מדוע זו הסיבוכיות.

אינדקס שיווי משקל במערך

link

עליכם לממש פונקציה בשם FindEquilibriumIndex אשר מקבלת פרמטר אחד:

1. arr - מערך של מספרים שלמים.

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

הפונקציה צריכה להחזיר true אם אינדקס כזה קיים, ו-false אחרת.

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

דגשים:

1. עבור איבר באינדקס 0, הסכום השמאלי הוא 0.
2. עבור איבר באינדקס האחרון, הסכום הימני הוא 0.
3. יש לממש את הפונקציה ביעילות.

בדיקת סכום זוג במערך ממוין

link

עליכם לממש פונקציה בשם HasPairWithSum אשר מקבלת שני פרמטרים:

1. arr (int[]) - מערך ממוין של מספרים שלמים.
2. target (int) - ערך המטרה.

הפונקציה צריכה לבדוק האם קיימים שני איברים שונים במערך arr שסכומם שווה ל-target.

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

החזרה:

1. true - אם קיים זוג איברים כזה.
2. false - אחרת.

הפרש מקסימלי במערך

link

עליכם לממש פונקציה בשם MaxDifference אשר מקבלת פרמטר אחד:

1. arr - מערך של מספרים שלמים (int[]).

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

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

דגשים

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

חיפוש בינארי במערך ממוין

link

עליכם לממש פונקציה בשם BinarySearch אשר מקבלת שני פרמטרים:

1. arr - מערך ממויין של מספרים שלמים (int[]).
2. target - המספר השלם שיש לחפש במערך (int).

הפונקציה צריכה להחזיר true אם target נמצא במערך arr, ו-false אחרת.

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

דגשים:

1. יש לממש את הפונקציה באמצעות אלגוריתם חיפוש בינארי.
2. המערך הנתון יהיה תמיד ממוין בסדר עולה.
3. אין להשתמש בפונקציות חיפוש מובנות של השפה (כמו Array.BinarySearch או List.Contains).

מציאת שיא מקומי במערך

link

עליכם לממש פונקציה בשם FindLocalPeak אשר מקבלת פרמטר אחד:

1. arr - מערך של מספרים שלמים.

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

הגדרה של שיא מקומי:

1. עבור איבר באינדקס i (שאינו איבר קצה), הוא שיא מקומי אם arr[i] > arr[i-1] וגם arr[i] > arr[i+1].
2. עבור האיבר הראשון (arr[0]), הוא שיא מקומי אם arr[0] > arr[1].
3. עבור האיבר האחרון (arr[n-1]), הוא שיא מקומי אם arr[n-1] > arr[n-2].

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

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