יש לי שאלה בסיבוכות והיית רוצה לדעת אם פתרתי אותה נכון

נתונה השיטה הבאה:

public static boolean what (int [] a, int [] b)
{
if (a.length != b.length)
return false;
for (int i= 0; i<a.length; i++)
for (int j=0; j<b.length; j++)
if (b[j] < a[i])
return false;
return true;
}

א' בהנחה שהמערכים מלאים במספרים שלמים מה מבצעת השיטה

ב מה סיבוכית זמן הריצה ומהי סיבוכיות המקום של השיטה, הסבירו

ג' כיתבו את השיטה מחדש שתבצע את מה שביצעה ב-א' בסיבוכות זמן ריצה קטנה יתר

התשובות שלי:

א' השיטה מחפשת האם ישנו מספר במערך b שהוא קטן יותר ממספר במערך a

ב' סיבוכיות של n בריבוע כיוון שעל כל איבר במערך a אנחנו עוברים של כל מערך b - הם זוהי סיבוכית הזמן, המקום או שניהם יחד ?

ג' אני היתי ממיין את שני המערכים אז זה יוצא פעמיים nlogn ובסה"כ nlogn ואז משווה את 2האיבר הכי גדול ממערך a לאיבר הכי קטן ממערך b

עוד משהו שחשבתי שאפשרי זה לעבר על כל מערך ולמצוא את המספר המקסימלי מ-a והמינימלי מ-b - סיבוכיות של פעמיים n

ומשווה ובסה"כ סיבוכיות של n

נערך 2014 בינואר 1211 שנים על-ידי booraz2012

א. הסברת מה השיטה עושה, אבל לא אמרת מה היא מחזירה (מתי אמת ומתי שקר?)

ב. זו סיבוכיות הזמן. סיבוכיות המקום היא כמה מקום בזכרון השיטה הזו דורשת.

ג. אחלה.

אפשר בבקשה הסבר על מה הייתה אמורה להיות התשובה לסעיף ב' ?

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

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

אז בתשובה לסעיף ב' התשובה שלי O(n²) נכונה ?

כן.

תודה רבה.