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

[falukky]

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² אבל איך אני יודע את סיבוכיות המקום ?

[QttP]

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

[falukky]

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

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

[QttP]

טוב.

[Gil28]

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

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

[falukky]

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

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

[Ligi]

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

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

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

[falukky]

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

[שניצל]

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

[falukky]

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

עידכון:

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

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

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

[שניצל]

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

[falukky]

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

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

[שניצל]

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

[Gil28]

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

[falukky]

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