שאלה 2 בתרגיל 2

Ron Bigman

unread,

Dec 29, 2012, 4:30:52 AM12/29/12

to algorithms-in-...@googlegroups.com

אהלן

בתרגיל נדרש למצוא אלגוריתם שסיבוכיות הזמן שלו תהיה

o(sum_I(Si))

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

תודה רבה

רון

Yackov Lubarsky

unread,

Dec 29, 2012, 9:07:33 AM12/29/12

to algorithms-in-...@googlegroups.com

מצטרף לשאלה

יעקב

Edo Liberty

unread,

Dec 30, 2012, 1:02:18 AM12/30/12

to algorithms-in-...@googlegroups.com

המטרה היא למצוא אלגוריתם עם זמן ריצה ודרישת זיכרון נמוכות ככל האפשר (כרגיל)

במקרה הזה זמן הריצה של הפרפרוסס הוא לפחות.
sum |S_i|
מכוון שצריך לקרוא אותם לפחות פעם אחת. (בהנחה שדגימה אינה אפשרית)
וזיכרון קטן אסימפטוטית מ
sum |S_i|

בקשר לשלב השני הדרישה היא לזמן ריצה קטן אסימפטוטית מ-
sum_{[I]} |S_i|

אני מקוה שזה עוזר.

Reply all

Reply to author

Forward