פורסם 2011 ביולי 1314 שנים יש לי עוד שאלה בקשר ל-skip-list .הפעולות על המבנה הזה הם בממוצע logn .עכשיו, אם נחליט שבכל רמה אנחנו מעלים כל איבר שני, יצא שבמקרה הגרוע כל הפעולות יהיו ב-logn.יש לי כאן טעות? אם לא, אז למה לא לדאוג לזה שהכל יתבצע בזמן דטרמינסטי logn ע"י זה שנעלה כל איבר שני ולא ע"י random
פורסם 2011 ביולי 1314 שנים מחבר יש לי עוד שאלה, כתוב לי באחד המבחנים:בנייה של עץ חיפוש בינארי מתוך רשימה של n מספרים לוקחת o(n^2)במקרה הגרוע.למה?
פורסם 2011 ביולי 1314 שנים 1. מה קורה אם אתה רוצה להוסיף איבר לאמצע הרשימה?2. אם אתה מוסיף את האיברים לפי הסדר (מהקטן לגדול), אתה תעבור 1+2+3+4+ ... + n איברים סך הכל (כל הוספה תעבור על כל האיברים שעד עכשיו הכנסת ברשימה). סכום סדרה חשבונית = o(n^2)
פורסם 2011 ביולי 1314 שנים אבל זה רק אם עשית את זה באופן לא יעיל. אפשר לבנות עץ חיפוש בינארי ב-(o(nlogn.
פורסם 2011 ביולי 1414 שנים מחבר תודה!! הבנתי..אפשר עוד כמה שאלות?1. בגרפים-איך מוצאים את המסלול הפשוט הכי ארוך כאשר יש משקולות על הצלעות/כאשר אין משקולות(נכון שזה כמו בגרף עם משקולות בגודל 1, אבל בטח אפשר לחסוף כאן בזמן ריצה..)-אני מחפש רק את הרעיון הכללי, אני פשוט לא מצליח לפתור שאלות בנושא הזה.. (למדנו רק פרים, קרוסקל, bfs, dfs)2. http://www.fastup.co.il/images/10874298.bmpלא הבנתי למה יש בעיה עם מתפחות זהים ומה הפתרון שהם מציעים?3. http://www.fastup.co.il/images/76021461.jpgלא כ"כ מסכם עם הפתרון שלהם שם..
פורסם 2011 ביולי 1414 שנים 1. זו בעיה NP-קשה, דהיינו אין אלגוריתם יעיל לפתרון שלה (אפשר להראות בקלות רדוקציה אליה מבעיית מציאת מסלול המילטוני).2. הרעיון באלגוריתם הוא שאם יש דלי עם יותר מ-k מפתחות, אז ממיינים את הדלי הזה שוב ע"י חלוקה שלו לעוד דליים באופן רקורסיבי. הבעיה היא שאם יש מפתחות זהים, אז בכל חלוקה לדליים המפתחות הזהים יפלו לתוך אותו דלי, ולכן תמיד יהיה לך דלי עם הרבה מפתחות. אז מה שעושים הוא לדאוג לשוני בין המפתחות האלו, אבל באופן שעדיין שומר על הסדר.
פורסם 2011 ביולי 1414 שנים מחבר אוקיי טוב לדעת..אז במקרה שמדובר על גרף מכוון ללא מעגלים כמו בשאלה המצורפת.אני יודע שמתחילים עם לעשות מיון טופולוגי ונניח שהתקבל המיון:v1 v2 ...vnאני תמיד חושב על הכיוון של לעשות רשימת צלעות נכנסות ואיכשהו להתקדם משם ותמיד נתקע בשלב הזה...אפשר רעיונות איך לחשוב על שאלות מהסוג הזה?http://www.fastup.co.il/images/46467590.bmp
פורסם 2011 ביולי 1414 שנים מחבר ועוד משהו..איך היינו עושים עם המשקולות היו על הצלעות(לא בהכרח קשיר אז אי אפשר להריץ קרוסקל/פרים)?
פורסם 2011 ביולי 1414 שנים מחבר טוב..הסתדרתי בסוף עם הגרף...רציתי לשאול שוב בקשר ל-skipList..החיפוש לוקח בממוצע o(logn).אפשר הסבר איך בדיוק מגיעים לזמן ריצה הזה
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.