פורסם 2013 במאי 1312 שנים שלום,יש לי שאלה שבה אני צריך לכתוב פונקציה שמקבלת מערך.יעילות המקום של הפתרון שלי תלויה בערכים הקיימים במערך (מערך של מספרים) ולא באורך המערך.כך שהמקסימום מקום תלוי ב- max int ובגודל של byte(ששניהם בעצם מס' קבועים).האם יעילות המקום נחשבת o(1) ?תודה
פורסם 2013 במאי 1312 שנים בעקרון כן, אלא אם מדובר באלגוריתם תיאורטי, כי אז בדרך כלל מתעלמים ממגבלות של המחשב. במקרה כזה משתמשים בגודל המספר בביטים כגודל הקלט. כלומר אם לדוגמה הקלט הוא x וזמן הריצה הוא O(x) אז בעצם בהנחה שבמספר יש n ביטים, זמן הריצה הוא O(2^n).
פורסם 2013 במאי 1312 שנים נשמע כאילו האלגוריתם שלך עקום. מה הבעיה ומה הפתרון שלך?בכל מקרה במצב כזה סיבוכיות המקום לינארית בקלט, כלומר (O(n
פורסם 2013 במאי 1312 שנים מחבר האלגוריתם לא עקום. זו הדרך היחידה להגיע בחומר שנלמד עד עכשיו בקורס ליעילות o(n) בזמן.לא הבנתי איך זה o(n) (המקום) אם זה לא תלוי בגודל המערך אלא בערכים הנמצאים בו :confused:
פורסם 2013 במאי 1312 שנים מחבר בעיקרון יש לי מערך של מספרים ואני צריך לדעת אם קיימים מספרים שנמצאים בדיוק X פעמים במערך (אם כן או לא ולא איזה או כמה)...
פורסם 2013 במאי 1312 שנים סיבוכיות המקום במקרה הזה קבועה במימוש נאיבי ואו קבועה או לינארית במימוש יעיל.
פורסם 2013 במאי 1312 שנים מחבר אז שוב אם מימשתי את זה כתלות בערכים במערך.כך שהמקסימום שלי הוא max_int ותלוי בערכים שנמצאים במערך ולא באורכו האם זה גם נחשב o(n) ?
פורסם 2013 במאי 1312 שנים יש לך איזו הנחה על טווח הערכים? אם כן אז ברור שטווח הערכים הוא חלק מהקלט. אם לא, באיזה גודל המערך שלך?
פורסם 2013 במאי 1312 שנים מחבר סבבה בידיוק מישהו הסביר לי למה זה o(n) ולא אין שום הנחה חוץ מזה שזה מערך של int.תודה...עכשיו אני רק מתלבט בין פתרון של סיבוכיות מקום 1 וסיבוכיות זמן nlogn לבין הפתרון הזה בו שניהם o(n)
פורסם 2013 במאי 1312 שנים בדרך כלל כשיש כמה אפשרויות, המימוש תלוי בהיכן הולכים להריץ את התוכנית. אם זה היה למשל חלק ממערכת חירום ברכב, כמובן ששווה להשקיע על זיכרון ולחסוך בזמן ריצה.במקרה שלך זה באמת לא משנה כי הכל כאן זניח ורץ מהר. בד"כ תבחר את זה עם סיבוכיות זמן הריצה הטובה ביותר.
פורסם 2013 במאי 1412 שנים אפשר להשתמש במקרה הזה ב-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)
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.