החיפוש הניב 87 תוצאות

על ידי Brk
19:49 17/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה דחופה
תגובות: 0
צפיות: 1655

שאלה דחופה

לגבי עבודה 5,איזון ערימות.עשיתי את העבודה וקיבלתי 85 עכשיו רציתי לדעת אם יש איזה סוג של עיקרון מאחורי איזון הערימה.בעיקרון אני זוכר את איזון הערימות לפי התוכנית שכתבתי כתהליך די טכני ללא עיקרון מאחורי זה לעומת האיתחול שמתבסס על עיקרון רקורסיבי של מציאת החציון של החציונים עד שמגיעים לקטעים בגודל n/k....
על ידי Brk
16:06 17/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה לגבי שאלה 4 בתרגול 11
תגובות: 2
צפיות: 2004

Re: שאלה לגבי שאלה 4 בתרגול 11

בשאלה אנחנו מתבקשים למיין n מחרוזות שאורכן לא קבוע ב- (O(n לפי סדר לקסיקוגרפי. בקורמן מופיעה אותה שאלה (8.3 בעמ' 158, במהדורה השנייה למי שממש מתעקש לבדוק :P). בתשובה שלהם הם אומרים שהפתרון שניתן בתרגול אינו נכון בהכרח. נכתב שם שהמקרה הגרוע ביותר הוא מחרוזת אחת באורך n/2 ושאר n/2 המחרוזות באורך 1. ו...
על ידי Brk
18:55 16/07/2010
פורום: - מבני נתונים 2010
נושא: עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו
תגובות: 2
צפיות: 2900

עבודה 5 והאלגוריתם למציאת האיבר ה-i בגודלו

שאלה: האלגוריתם למציאת האיבר הn/k בגודלו מתבצע על ידי מציאת האיבר הn/2 בגודלו ואז באופן רקורסיבי מציאת החציונים בשאר תתי המערכים.נמשיך בתהליך הזה עד אשר נגיע לתתי מערכים בגודל n/k . בראש הקבוצה הראשונה בגודל n/k ישב האיבר ה-n/k ?(כערימת מקסימום כמובן) אם ידרשו למצוא את האיבר שמופיע n/k פעמיים הרי שז...
על ידי Brk
16:13 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4557

Re: בנייה של עץ AVL

שאלה נוספת (יש הרבה היום :))
מישהוא יודע מה זמן הבנייה של עץ B-tree ?
על ידי Brk
15:55 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4557

Re: בנייה של עץ AVL

אני חושב כמוך.. השימוש יפחת. אגב, באותו מבחן איך הוכחת בשאלה 3 (הראשונה חח) זאת עם העץ פורש, את סעיף א'? בשאלה 3 ששם מציגים לך את האלגוריתם של קרוסקל למציאת MST דילגתי על זה,לא נראה לי שנצטרך להוכיח נכונות של אלגוריתם במבחן. פעם דרשו מהם הוכחות היום זה יותר תכלס אז זה נראה לי מוזר להתעקב על זה,מה ש...
על ידי Brk
15:32 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4557

Re: בנייה של עץ AVL

פעולת הכנסה של skipList היא O(logn) בממוצע לכן, הכנסת n איברים לרשימת דילוגים תיקח O(nlogn) בממוצע אוקי תודה שאלה נוספת זה ממבחן 2004 שאלה 3 (25%) שאלה זו עוסקת בעצי-B א) (7 נק') שרטט עץ-B בו t=2 (עץ 1,2,3) אשר מכיל את המפתחות A,B,C,D,G,H,K,,M,R,W,Z ב) (8 נק') שרטט את העץ המתקבל לאחר הוצאה של האיבר...
על ידי Brk
15:15 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4557

Re: בנייה של עץ AVL

eliorar כתב:אם אין לך שום הנחה על הקלט, אז זהו החסם הנמוך ביותר
אוקי תודה :)
וזמן בנייה סטנדרטי של skiplist זה גם כך או פחות?
על ידי Brk
14:59 16/07/2010
פורום: - מבני נתונים 2010
נושא: בנייה של עץ AVL
תגובות: 8
צפיות: 4557

בנייה של עץ AVL

זמן בנייה של עץ AVL ממערך בן n איברים לא ממוינים הוא nlogn נכון?
אין מצב לחסם יותר נמוך מכך?
על ידי Brk
13:11 16/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה
תגובות: 5
צפיות: 3384

Re: שאלה

rubichi כתב:אני חושב שהדבר הראשון שמתבקש הוא למיין את המערך ב nlogn
כעת, לאחר שהוא ממויין אני מצליח לחשוב על לעבור על כל הזוגות ועבור כל זוג לחפש חיפוש בינארי את הסכום שלהם -O(n^2(logn)) I
זה לא ממש אופטימלי אם זה יותר מn בריבוע?
על ידי Brk
12:48 16/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה
תגובות: 5
צפיות: 3384

Re: שאלה

eliorar כתב:מה האיברים במערך? שלמים? בטווח מסויים?
שלמים
על ידי Brk
11:52 16/07/2010
פורום: - מבני נתונים 2010
נושא: שאלה
תגובות: 5
צפיות: 3384

שאלה

נתקלתי בשאלה הבאה: דומה לקצת לשאלה 4 שהופיע בעבודה 6 רק יותר קשה לטעמי. נתון מערך בגודל n הצע אלגוריתם יעיל מבחינת סיבוכיות זמן . המכריע האם קיימים במערך שלושה איברים במערך x,y,z כך ש: x+y=z.שלושת האיברים אינם נתונים ונמצאים במערך עצמו.
האיברים במערך הם שלמים

יש למישהוא רעיון איך לפתור את זה :D ?
על ידי Brk
00:31 16/07/2010
פורום: - מבני נתונים 2010
נושא: טבלאות גיבוב - שאלה
תגובות: 8
צפיות: 5116

Re: טבלאות גיבוב - שאלה

אחלה, תודה רבה רונן, אם זה היה תלוי בי - הייתי שולח אותך לתואר שני ובמקביל מצרף אותך לצוות המתרגלים שלנו :) Brk, סבבה, כלומר - פשוט לא לשכוח שכששואלים על O של 1 בממוצע - לחשוב מיד על טבלת האש. ככה, לא? תודה :) כן!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!...
על ידי Brk
23:59 15/07/2010
פורום: - מבני נתונים 2010
נושא: טבלאות גיבוב - שאלה
תגובות: 8
צפיות: 5116

Re: טבלאות גיבוב - שאלה

זה בהנחה ויש לי פונקציה שמוגדרת "טובה", כלומר - אני מגיע לתא הרלוונטי שאני מחפש בזמן יחסית קבוע ע"י שימוש בפונקציה? זה התחיל להתבהר לי אחרי שקראתי איזשהו סיכום לפני כמה דקות. למשל בשאלה 3 שהופיעה במבחן - אני מגדיר טבלת האש בגודל N בריבוע ופונקציה האש שמקשרת בין כל מספר שהיא מקבלת לכתובת הזיכרון שלו...
על ידי Brk
21:48 15/07/2010
פורום: - מבני נתונים 2010
נושא: קיץ 2004
תגובות: 0
צפיות: 1456

קיץ 2004

בשאלה 3: נתון אלגוריתם חדש למציאת עץ פורש מינימלי בגרף ממושקל { V,E,W} = G: מאתחלים עץ ריק T ממיינים את הקשתות מ-E לתור Q. כל עוד העץ אינו מכיל N-1 צלעות, מוציאים את הצלע e המינימלית ב Q. אם e לא סוגרת מעגל עם הקשתות שכבר בתוך העץ T, מוסיפים אותה לעץ T. מחזירים את T כעץ פורש מינימלי. ג) (7 נק') אם כ...

עבור לחיפוש מתקדם