חידה מעצבנת שאחי הקטן שאל

[פינחס רוזנצוויג]

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

במספרים גדולים מאוד הסכום יגלוש מעבר לגודל של INT ועלול גם לגלוש מעבר לגודל LONG

 

[UU]

בונים מערך מאופס בגודל N
עוברים על מערך המספרים הלא ממוינים
מסמנים 1 בכל אינדקס שהערך שלו קיים במערך...

זה הפתרון הכי פשוט
(זה יעלה עוד O מקוםׂ)
ׂ

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

 

[פינחס רוזנצוויג]

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

O+O = O
אסמפטוטית, סדר הגודל נשאר זהה.

 

[s976]

....

 

[פרוגיוזרית]

(זה יעלה עוד O מקוםׂ)

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

 

[s976]

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

מאמין שזה הכיוון.
נגמר לי המקום בפתק. אבל זה כבר טריוויאלי - נוסחת שורשים

 

[B HAPPY]

@פרוגיוזרית - הפתרון זה מה שהציע @s976 ?

 

[פרוגיוזרית]

@פרוגיוזרית - הפתרון זה מה שהציע @s976 ?

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

 

[פררו רושה]

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

 

[s976]

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

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

 

[פררו רושה]

במבוא למדעי המחשב

אוףףף,
אני לא רוצה להסיט את הנושא, אז שאלה אחרונה בל"נ,
מישהו יודע אם זה קורס חובה לבעלי תעודה של מה"ט?
כי ממש חסר לי הידע הזה, וכבר חשבתי שאני הולכת להשלים אותו בסמסטר הקרוב

 

[s976]

אוףףף,
אני לא רוצה להסיט את הנושא, אז שאלה אחרונה בל"נ,
מישהו יודע אם זה קורס חובה לבעלי תעודה של מה"ט?
כי ממש חסר לי הידע הזה, וכבר חשבתי שאני הולכת להשלים אותו בסמסטר הקרוב

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

 

[פררו רושה]

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

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

 

[פרוגיוזרית]

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

גם במבני נתונים ומבוא לאלגוריתמים לומדים את זה. לא תורה גדולה.

 

[B HAPPY]

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

 

[פרוגיוזרית]

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

אכן. גם ברור וגם נכון

 

[@qwerty]

@פררו רושה בדיוק ראיתי....
https://campus.gov.il/course/urse-v1tauacd-rfp4-tau-data-structures/‏
זה מנחים מעולים, סתם אם מעניין אותך.

 

[5127109]

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

זה כל כך נכון!!!!