שאלה 4 קל מדי?

ohad cohen Fri Apr 17, 2009 5:23 pm

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

AViG Fri Apr 17, 2009 5:41 pm

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

זה לא מובן כי אתה עדין חייב לעבור על כל אברי הרשימה ולבדוק אותם אחד אחד אז שום מיון/חיפוש יעיל שלמדנו לא יכול לעזור.
ה worst case שכל האיברים ברשימה שונים זה מזה מאוד מזכיר bubble sort ולכן אם אני לא טועה היעילות היא תמיד O של n בריבוע

itaytak Sat Apr 18, 2009 10:13 am

בגדול אפשר לעשות את 4 בגירסא של bucket sort ולקבל יעילות לינארית (הרי נתון טווח המיספרים 200-800 ולכן עבור כל מספר ברשימה ניתן לבדוק אם ערך האנידקס הזהה במערך גדול מאפס או לא, אם כן מוצאים מהרשימה, אם לא מוספים 1)
אך במקרה זה אנו עלולים להשתמש במקום רב בזיכרון לחינם (כיוון שנשתמש במערך לוקאלי בפונקציה, אין זה קריטי לטעמי...)
הכל טוב ויפה אך במידה ונבחר בשיטה זו לא נצטרך להשתמש בעובדה שניתן לעבור על איברי הרשימה משני הכיוונים ולכן אין לי מושג מה רוצים מהחיים שלנו! scratch

**Admin** Sat Apr 18, 2009 9:29 pm

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

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

ohad cohen Sat Apr 18, 2009 10:42 pm

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

SHAHARC Sun Apr 19, 2009 1:39 am

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

שאלה 4 קל מדי?

שאלה 4 קל מדי?

Re: שאלה 4 קל מדי?

יעילויות, סיבוכיות ושאר ירוקות שאנחנו לא אוהבים לאכול!

Re: שאלה 4 קל מדי?

Re: שאלה 4 קל מדי?

לדעתי הם רוצים שנעשה פה כמו מיון דליים