חידה נחמדה:

[dragonight4]

התשובה

אז ככה, עוברים על הטקסט פעם אחת, - (O(N לכל מילה מחשבים את הhashcode ומכניסים לhashtable בגודל N של מונים כאשר המפתח זה הhashcode של המילה, - (O(1 אם כבר קיימת מילה כזאת אז רק מעלים את המונה באחד, בסוף עוברים על הhashtable ומוצאים מקסימום - (O(N לסיכום: - (O(N N*1+N אני מקווה שיש לכם מושג מה זה hashtable בקצרה ההכנסה היא חד חד ערכית והפעולות הם (O(1

 

[cyberia2ooo]

אממ לא בדיוק נכון

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

 

[dragonight4]

hash עם טיפול בהתנגשויות

בשביל התנגשויות: 1 - hash עם טיפול בהתנגשויות, כמו דילוגים או שירשור זה עדיין (O(1 חוץ מזה, הטבלה בגודל N שזה אורך הטקסט באותיות ומכניסים בה מילים, שזה הרבה פחות ממספר התאים שיש בה. כלומר ההתנגשויות כל כך מעטות. 2 - או שימוש בperfect hash, כלומר פעמיים hash, ולבנות hashtable ולמצוא פונקציית perfect hash רק לאלא שמתנגשים באותו תא, שזה בודדים מאוד. ולמצוא פונקציה כזאת באקראי, סיכויים גדולים מאוד שתמצא בנסיון הראשון או השני, לכן זה עדיין (O(1

 

[the new L]

מעשית כנראה

שזה פיתרון טוב, רק תיאורטית הוא לא באמת בסיבוכיות לינארית כמו שנדרש בשאלה.

 

[the new L]

בשביל זה

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

 

[idansof]

אין מגבלה לשימוש בשפות אקזוטיות?

אם כך, נגדיר שפת תכנות A, בה ההוראות מבוטאות באות הראשונה בשורה, במקרה שלנו, O מוציאה פלט לstdout. נגדיר שפת תכנות B, שהיא וריאציה שלה, לה קיימת הוראה חלופית/פונקצית ספריה המבוטאת באות S, אשר פועלת בצורה זהה לO, למעט הוספת קידומת OS לכל שורה בפלט

OSHello world​