עבור לתוכן

סיבוכיות זמן ומקום - שאלה

Featured Replies

פורסם

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

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


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

נערך על-ידי booraz2012

פורסם

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

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

ג. אחלה.

פורסם
  • מחבר

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

פורסם

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

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

פורסם
  • מחבר

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

פורסם
  • מחבר

תודה רבה.

ארכיון

דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.

דיונים חדשים