אתחול המבנה נתונים

מנהל: TA_Isana

אתחול המבנה נתונים

הודעהעל ידי asaf90 » 03:20 19/05/2010

אם לסמוך רגע על ויקיפדיה אז מישהו טוען שמה שחסם תחתון של כל מיון יהיה nlogn
אז אלא אם הם טועים או שיש איזה אלגוריתם מיון שמוסתר ממני למיטב ידיעתי זה הסיבוכיות הכי טובה שאנחנו יכולים לקבל
אז למה המבנה נתונים שביקשתם אמור לתמוך בסיבוכיות נמוכה יותר?
asaf90
 
הודעות: 13
הצטרף: 01:17 13/11/2009

Re: אתחול המבנה נתונים

הודעהעל ידי TA_Ariel » 10:30 19/05/2010

כי הוא לא חייב למיין.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: אתחול המבנה נתונים

הודעהעל ידי asaf90 » 16:07 19/05/2010

לא לפי ההסבר שפירסמתם בעבודה
מתחת להגדרה של המבנה רשום הסדר של האיברים והם נראים לי דיי ממויינים
גם האינדקס שקוראים לו הוא אינדקס לפי הסדר גודל
לפחות ככה זה מצויין בהסבר בעבודה אם זה לא אמור להיות ככה אשמח לדעת
asaf90
 
הודעות: 13
הצטרף: 01:17 13/11/2009

Re: אתחול המבנה נתונים

הודעהעל ידי TA_Ariel » 16:32 19/05/2010

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

בהסבר כתבתנו את האיברים בסדר ממויין כדי להסביר מה הכוונה לאיברים במקומות המיוחדים.

אז נכון שמיון היה פותר את הבעיה אבל זה לא אומר שחסם תחתון על מיון הוא גם חסם על הבעיה בעבודה,
זה אומר שמיון הוא חסם עליון לבעיה.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: אתחול המבנה נתונים

הודעהעל ידי asaf90 » 17:32 19/05/2010

אילו מקומות מיוחדים התכוונת?
בהסבר רשום תחזיר את האיבר הרביעי ומחזירים את האיבר שנמצא במקום הרביעי(לפי מיון) אתה מתכוון בעצם שזה סתם לפי המחשה ואין צורך להחזיר איבר רביעי ממוין פשוט להחזיר את האיבר הרביעי?
asaf90
 
הודעות: 13
הצטרף: 01:17 13/11/2009

Re: אתחול המבנה נתונים

הודעהעל ידי TA_Ariel » 19:46 19/05/2010

צריך להחזיר את האיבר הרביעי במיון אבל לא צריך למיין בשביל זה.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: אתחול המבנה נתונים

הודעהעל ידי asaf90 » 22:24 19/05/2010

אז נגיד יש לי 100 איברים איך אני מוצא את האיבר ה16 במיון בלי למיין?
איך בכלל אפשר להחזיר איבר עפ מיון אם אתה לא ממיין קודם? כמובן בלי קשר למקסימום ומינימום שאותם קל למדי לגלות כשיוצרים את המבנה
asaf90
 
הודעות: 13
הצטרף: 01:17 13/11/2009

Re: אתחול המבנה נתונים

הודעהעל ידי TA_Ariel » 23:47 19/05/2010

למדתם בכיתה מציאת חציון והאיבר הi- בגודלו בזמן לינארי בממוצע. תנסה לחשוב איך משתמשים בזה כאן.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009

Re: אתחול המבנה נתונים

הודעהעל ידי asaf90 » 23:52 19/05/2010

אבל אתם רוצים שאני אחזיר איבר באינדקס i בזמן קבוע ככה שגם אם הבנתי אותך נכון וגם אם לא זה לא עומד בסיבוכיות
asaf90
 
הודעות: 13
הצטרף: 01:17 13/11/2009

Re: אתחול המבנה נתונים

הודעהעל ידי TA_Ariel » 23:55 19/05/2010

אבל יש לך את הזמן הזה באתחול.
TA_Ariel
 
הודעות: 261
הצטרף: 23:53 22/04/2009


חזור אל - מבני נתונים 2010

מי מחובר

משתמשים הגולשים בפורום זה: אין משתמשים רשומים ו 3 אורחים

cron