שלום,

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

אבל נתנו לנו קטע קוד, שעלינו "לשפר" כך שיתבצעו פחות בדיקות השוואה (כלומר פחות בדיקות של גדול ושווה וכאלה)

הקוד:

http://pastebin.com/bqcmXuag

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

והראות מפורשות של התרגיל:

כתבו את השיטה כך שתבצע את מה שביצעה בעזרת פחות פעולות השוואה.

שימו לב, עליכם לכתוב שיטה המייעלת את השיטה במספר קבוע ולא בסדר גודל.

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

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

תודה רבה

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

תעשה את ההשוואות בצורה רנדומאלית, ואז יש לך ממוצע הסתברותי קטן יותר של השוואות.

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

ההסבר שלך לא ממש מאפשר להבין הרבה.

בנוסף, אתה מקצה זיכרון ב-(O(1 אז אין באמת אפשרות לשפר את סיבוכיות הזכרון

כרגע יעילות הזכרון היא O(1), אבל הכוונה של השאלה היא שצריך להפוך אותו כנראה ל O(n) בשביל לעמוד במטרת השאלה.

ובכל מקרה אם הערך קטן אני עובר לאיטרציה הבאה, כי ההמשך זה else

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

אז זו אמנם דרך קצת עקומה אבל הנה רעיון:

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

-תבנה מערך נוסף שאורכו הוא טווח הערכים האפשרי, אם מדובר למשל על יצוג מספרים של 8 ביט (0-255 או 128-127- עבור שליליים גם) אז צריך מערך באורך 256.

-תאתחל את המערך כבוליאני שהכל בו false או שהכל בו אפסים.

-תעבור על כל המספרים במערך המקורי ועבור כל אחד "תדליק" את התא המתאים לו במערך האינדקסים ע"י הפיכתו ל-true או 1.

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

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

כרגע יעילות הזכרון היא O(1), אבל הכוונה של השאלה היא שצריך להפוך אותו כנראה ל O(n) בשביל לעמוד במטרת השאלה.

ואיפה בדיוק השיפור פה?

עריכה:

תשובה לדבלין, סיבוכיות הזמן של מה שאתה מציע תלוי ביצוג והיא לא יעילה לחלוטין

הם לא ביקשו לשפר את סיבוכיות המקום \. הזמן

הם ביקשו שאני יבצע פחות פעולות השוואה.

אתה חייב לפחות פעולת השוואה אחת לדעתי בכל פעם, אחרת איך תדגום איפה אתה עומד?

אני חולק עליך Access denied.

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

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

בכל אופן, שאלתי מישהו שפתר את התשובה (ומסרב לספר לי אותה )

הוא אמר שאלו הם לא הדרכים

והמערך הוא של int בכל מקרה

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

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

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

רמז:

ע"י פעולות ביטים ניתן לבצע min, max וגם selection ללא השוואות.

תשובה:

כנראה שהם מתכוונים לזה: http://aggregate.org/MAGIC/#Integer%20Minimum%20or%20Maximum

רקע:

במעבדים מודרנים branch הוא יקר ולכן הרבה פעמים עדיף למנוע את זה.

מצד שני, בהרבה מעבדים מודרנים יש שיטות לבצע min ו-max ללא branch, וקומפיילרים מודרנים מקמפלים לקוד יעיל כאשר הם מזהים פעולת min או max. לדוגמא ע"י predicated move, או פעולת ביטים דומות, או אפילו בעולות min,max ב-ISA. על כן זה תרגיל מצויין לדעת איך עושים את זה ולמה זה עובד, אבל בקוד אמיתי עדיף להמנע מטריקים כאלה אלא אם יש סיבה טובה ומדידות