שאלה לגבי יעילות מקום

[Shoko]

שלום,

יש לי שאלה שבה אני צריך לכתוב פונקציה שמקבלת מערך.

יעילות המקום של הפתרון שלי תלויה בערכים הקיימים במערך (מערך של מספרים) ולא באורך המערך.

כך שהמקסימום מקום תלוי ב- max int ובגודל של byte(ששניהם בעצם מס' קבועים).

האם יעילות המקום נחשבת o(1) ?

תודה

[שניצל]

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

[Gil28]

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

בכל מקרה במצב כזה סיבוכיות המקום לינארית בקלט, כלומר (O(n

[Shoko]

האלגוריתם לא עקום. זו הדרך היחידה להגיע בחומר שנלמד עד עכשיו בקורס ליעילות o(n) בזמן.

לא הבנתי איך זה o(n) (המקום) אם זה לא תלוי בגודל המערך אלא בערכים הנמצאים בו :confused:

[שניצל]

יעזור אם תכתוב יותר פרטים על הבעיה.

[Shoko]

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

[Gil28]

סיבוכיות המקום במקרה הזה קבועה במימוש נאיבי ואו קבועה או לינארית במימוש יעיל.

[Shoko]

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

כך שהמקסימום שלי הוא max_int ותלוי בערכים שנמצאים במערך ולא באורכו האם זה גם נחשב o(n) ?

[Gil28]

איך בדיוק מימשת את זה עם תלות בערך של האיברים?

[Shoko]

יש קאונטרים לכל הטווח של הערכים...

[Gil28]

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

[Shoko]

סבבה בידיוק מישהו הסביר לי למה זה o(n) ולא אין שום הנחה חוץ מזה שזה מערך של int.

תודה...

עכשיו אני רק מתלבט בין פתרון של סיבוכיות מקום 1 וסיבוכיות זמן nlogn לבין הפתרון הזה בו שניהם o(n)

[Gil28]

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

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

[LiorP23]

אפשר להשתמש במקרה הזה ב-HashMap שממפה int ל-int

עבור כל ערך תבדוק אם הוא קיים כבר ב-HashMap

אם לא, תוסיף אותו כ-Key עם Value שהוא 0

אם כן תקדם את ה-Value שלו ב-1.

זמן הריצה של האלגוריתם עד כאן הוא O(n) מכיוון שרצים על כל ערך פעם אחת בדיוק

לאחר מכן ניתן לעבור על כל ה-Key-Value ב-HashMap ולבדוק האם ה-Value מתאים ל-X שאתה מחפש אם כן ה-Key הוא המספר שאתה רוצה.

במקרה הטוב ביותר שכל הערכים במערך המקורי שלך הם זהים הלולאה השנייה תרוץ פעם אחת

במקרה הגרוע ביותר שכל הערכים במערך המקורי שלך הם שונים אחד מהשני הלולאה השנייה תרוץ O(n)

וכמובן ש-O(n)+O(n) זה עדיין O(n)