עבור לתוכן

מהי סיבוכיות המקום של הפונקציה הבאה ?

Featured Replies

פורסם

public void what(int[] _arr){
int x = _arr[0];
int y = _arr[0];
for (int i=1; i<_arr.length; i++)
{
if (_arr[i] < x)
x = _arr[i];
else if (_arr[i] > y)
y = _arr[i];
}
System.out.println (x + " " + y);
}

סיבוכיות הזמן היא n² אבל איך אני יודע את סיבוכיות המקום ?

  • תגובות 32
  • צפיות 4.8k
  • נוצר
  • תגובה אחרונה
פורסם

למה אתה חושב שזו סיבוכיות הזמן?

פורסם
  • מחבר

אני צריל לענות על השאלה מה סיבוכיות זמן הריצה ומהי סיבוכיות המקום של השיטה ?

ואז לכתוב את הפונקציה המייעלת אותה במספר קבוע ולא בסדר גודל (מותר לשנות את סיבוכיות המקום)

פורסם

טוב.

פורסם

תאר לי מה עושה האלגוריתם במילים ואיך הוא עושה את זה.

בנוסף, תאר לי את מספר ההשוואות שמבוצעות בכל איטרציה במקרה הטוב ובמקרה הגרוע.

פורסם
  • מחבר

מוצא מספר מינימום ומקסימום.

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

פורסם

תחשוב על זה אתה עובר על המערך פעם אחת ועורך מספר השוואות קבוע...

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

תנסה לחשוב על התשובה ואם לא תצליח אני אעזור לך יותר.

פורסם
  • מחבר

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

פורסם

מי אמר שאתה צריך לחשוב על משהו "עם פחות הקצאות זכרון"? השאלה היא רק כמה הקצאות זכרון יש לך.

פורסם
  • מחבר

עידכנתי את השאלה, הייתי בטוח שפירסמתי אותה.

עידכון:

יש איזשהי בעיה וזה שומר את השינויים ולא מראה אותם אז אני רושם פה:

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

2. כתבו את השיטה כך כך שתבצע את מה שביצעה בסעיף א' בעזרת פחות פעולות השוואה. שימו לב, עליכם לכתוב שיטה המייעלת את השיטה מסעיף א במספר קבוע ולא בסדר גודל!

פורסם

סיים קודם את 1. למה החלטת שסיבוכיות הזמן היא n^2?

פורסם
  • מחבר

נכון טעות שלי, זה n.

יש לי הקצאת זיכון ל-2 משתנים ו-2 תנאים עם אז איך אני מחשב את סיבוכיות הזמן ?

פורסם

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

פורסם

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

פורסם
  • מחבר

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

ארכיון

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

דיונים חדשים