סיבוכיות של פעולות שונות

סיבוכיות של פעולות שונות

ophir (guest) 11 Jul 2015 09:28

אהלן, להלן שאלה מועד ב' סמסטר ב' 2012:

למדנו שסיבוכיות ממוצעת של הפעלת פונקציית האש בפייתון (על כל דבר) היא בO של קבוע.
אבל פה נדרשת התייחסות גם לאורך המילים. שאלתי - כיצד נגדיר את הסיבוכיות עבור הפעלה של hash על מחרוזת באורך m? (האם מדובר לפחות בO של m או כמו שאותנו לימדו - בזמן קבוע)
ובנוסף, מה היא הסיבוכיות של הפיכת אובייקט למחרוזת? האם מדובר בO של אורך האובייקט בתווים?
וכנ"ל לגבי join כשמדובר במחרוזות (האם החישוביות של איחוד שתי מילים באורכים n,m היא כמו חיבור של 2 רשימות באורכים הנ"ל?).
תודה

Re: סיבוכיות של פעולות שונות

benny_chor 11 Jul 2015 10:11

Operation on long strings (say those exceeding one word in memory) require at the very least to go over these strings.
So if the string is of length m and is over a standard character set (say ascii), it takes m operations just to read it. This applies
to Python's hash as well. So in general hashing an m long string will take O(m) operations.

student (guest) 12 Jul 2015 11:41

אז אם ממפים מחרוזות לטבלת האש. הכנסה וחיפוש בטבלת האש לא יהיו O(1)?
אלא תלויים באורך המחרוזת שעליה מבצעים את ההאש?

benny_chor 12 Jul 2015 12:08

In general, hashing an m long string will take O(m) operations.

If m chars fit into one computer word, we can treat this as a constant number of operations.
This does not hold for longer values of m.