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

[שניצל]

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

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

[falukky]

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

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

[שניצל]

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

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

[falukky]

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

[Ligi]

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

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

[שניצל]

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

[falukky]

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

[Gil28]

מעבר למערך שאתה מקבל כקלט.

[falukky]

??

[שניצל]

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

[falukky]

2 מקומות ?

[Gil28]

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

[falukky]

הבנתי.

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

[Gil28]

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

[falukky]

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

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