עבור לתוכן

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

Featured Replies

פורסם

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

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

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

אז כאן יש 2 משתנים x ו-y ז"א סיבוכיות המקום היא O של 2 ?

מה קורה עם התנאים וההדפסה ?

פורסם

מה זה (O(2? להזכירך סיבוכיות מקום זה בדיוק כמו סיבוכיות זמן. אי פעם כתבת שמשהו הוא בסיבוכיות זמן (O(2?

ברצינות: למדת בכלל מה זה סיבוכיות מקום? לא הראו לכם תרגילים בהם מחשבים את זה?

פורסם
  • מחבר

הראו אבל זה משהו שלא ממש תפסתי בניגוד לסיבוכיות זמן

פורסם

אם אני לא טועה זה כמה מקום אתה תופס בכל זמן נתון...

עכשיו זה תופס N +2 ואני מאמין שהם רוצים שתקטין את זה.

פורסם

בשום מקום הם לא רצו להקטין את סיבוכיות המקום. רק את מספר פעולות ההשוואה.

פורסם
  • מחבר

אבל עדיין לא הבנתי מה סיבוכיות המקום כאן ? n + 2 ?

פורסם
  • מחבר

??

פורסם

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

פורסם
  • מחבר

2 מקומות ?

פורסם

נכון. מה שנקרא זיכרון קבוע או O של 1.

פורסם
  • מחבר

הבנתי.

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

פורסם

מי אמר שאתה צריך פחות מ-2 משתנים?

פורסם
  • מחבר

סליחה, בעזרת פחות פעולות השוואה:

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

ארכיון

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

דיונים חדשים