יש לי עוד שאלה בקשר ל-skip-list .

הפעולות על המבנה הזה הם בממוצע logn .

עכשיו, אם נחליט שבכל רמה אנחנו מעלים כל איבר שני, יצא שבמקרה הגרוע כל הפעולות יהיו ב-logn.

יש לי כאן טעות? אם לא, אז למה לא לדאוג לזה שהכל יתבצע בזמן דטרמינסטי logn ע"י זה שנעלה כל איבר שני ולא ע"י random

יש לי עוד שאלה, כתוב לי באחד המבחנים:

בנייה של עץ חיפוש בינארי מתוך רשימה של n מספרים לוקחת o(n^2)

במקרה הגרוע.

למה?

1. מה קורה אם אתה רוצה להוסיף איבר לאמצע הרשימה?

2. אם אתה מוסיף את האיברים לפי הסדר (מהקטן לגדול), אתה תעבור 1+2+3+4+ ... + n איברים סך הכל (כל הוספה תעבור על כל האיברים שעד עכשיו הכנסת ברשימה). סכום סדרה חשבונית = o(n^2)

אבל זה רק אם עשית את זה באופן לא יעיל. אפשר לבנות עץ חיפוש בינארי ב-(o(nlogn.

תודה!! הבנתי..

אפשר עוד כמה שאלות?

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

(למדנו רק פרים, קרוסקל, bfs, dfs)

2. http://www.fastup.co.il/images/10874298.bmp

לא הבנתי למה יש בעיה עם מתפחות זהים ומה הפתרון שהם מציעים?

3. http://www.fastup.co.il/images/76021461.jpg

לא כ"כ מסכם עם הפתרון שלהם שם..

לא צריך בסוף את שאלה 3, הבנתי את הטעות שלי...

1. זו בעיה NP-קשה, דהיינו אין אלגוריתם יעיל לפתרון שלה (אפשר להראות בקלות רדוקציה אליה מבעיית מציאת מסלול המילטוני).

2. הרעיון באלגוריתם הוא שאם יש דלי עם יותר מ-k מפתחות, אז ממיינים את הדלי הזה שוב ע"י חלוקה שלו לעוד דליים באופן רקורסיבי. הבעיה היא שאם יש מפתחות זהים, אז בכל חלוקה לדליים המפתחות הזהים יפלו לתוך אותו דלי, ולכן תמיד יהיה לך דלי עם הרבה מפתחות. אז מה שעושים הוא לדאוג לשוני בין המפתחות האלו, אבל באופן שעדיין שומר על הסדר.

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

אני יודע שמתחילים עם לעשות מיון טופולוגי ונניח שהתקבל המיון:

v1 v2 ...vn

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

אפשר רעיונות איך לחשוב על שאלות מהסוג הזה?

http://www.fastup.co.il/images/46467590.bmp

ועוד משהו..איך היינו עושים עם המשקולות היו על הצלעות(לא בהכרח קשיר אז אי אפשר להריץ קרוסקל/פרים)?

טוב..הסתדרתי בסוף עם הגרף...

רציתי לשאול שוב בקשר ל-skipList..

החיפוש לוקח בממוצע o(logn).

אפשר הסבר איך בדיוק מגיעים לזמן ריצה הזה