שאלה 4 קל מדי?

צפה בנושא הקודם צפה בנושא הבא Go down

שאלה 4 קל מדי?

הודעה  ohad cohen on Fri Apr 17, 2009 5:23 pm

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

מספר הודעות : 6
Join date : 10.04.09

צפה בפרופיל המשתמש

חזרה למעלה Go down

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

הודעה  AViG on Fri Apr 17, 2009 5:41 pm

גם אני לא הבנתי את היעילות פה, גם אם אתה עושה חיפוש על חצי מהרשימה , (זה אומר שאתה הולך מההתחלה והסוף ביחד עד שהפוינטרים שווים), אז אתה עדין באותה יעילות כמו ללכת ישירות מהסוף להתחלה כי במקום לעשות פעולה 1 כל פעם אתה עושה 2 בכל איטרציה Neutral זה לא מובן כי אתה עדין חייב לעבור על כל אברי הרשימה ולבדוק אותם אחד אחד אז שום מיון/חיפוש יעיל שלמדנו לא יכול לעזור.
ה worst case שכל האיברים ברשימה שונים זה מזה מאוד מזכיר bubble sort ולכן אם אני לא טועה היעילות היא תמיד O של n בריבוע
avatar
AViG
מתפקד בקושי
מתפקד בקושי

מספר הודעות : 2
Join date : 13.04.09

צפה בפרופיל המשתמש

חזרה למעלה Go down

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

הודעה  itaytak on Sat Apr 18, 2009 10:13 am

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

מספר הודעות : 1
Join date : 08.04.09

צפה בפרופיל המשתמש

חזרה למעלה Go down

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

הודעה  Admin on Sat Apr 18, 2009 9:29 pm

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

מספר הודעות : 62
Join date : 08.04.09
Age : 32

צפה בפרופיל המשתמש http://csmta.forumhebrew.com

חזרה למעלה Go down

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

הודעה  ohad cohen on Sat Apr 18, 2009 10:42 pm

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

מספר הודעות : 6
Join date : 10.04.09

צפה בפרופיל המשתמש

חזרה למעלה Go down

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

הודעה  SHAHARC on Sun Apr 19, 2009 1:39 am

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

SHAHARC
מתפקד בקושי
מתפקד בקושי

מספר הודעות : 2
Join date : 14.04.09

צפה בפרופיל המשתמש

חזרה למעלה Go down

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


 
Permissions in this forum:
אתה לא יכול להגיב לנושאים בפורום זה