Recent Forum Posts
From categories:
page 1123...next »

מצטרף לשאלה, משהו שיודע ויכול לעזור?

by אלון (guest), 10 Dec 2016 16:20
ליהי (guest) 10 Dec 2016 14:41
in discussion Fall 2016/7 / HW3 Q3 » סעיף ג SELECTION SORT

היי,
לא הבנתי את השאלה ולא הבנתי את התשובה.
האם הכוונה היא שגם במקרה הטוב ביותר של slection sort הסיבוכיות היא O(n^2), ויש להוכיח את הטענה ע״י מציאת רשימה ביטונית שתניב את זה?
ואם לא אז מישהו יכול להסביר לי מה הכוונה?
כי מבחינתי במקרה הטוב של selection sort הסיבוכיות היא O(n) וזה קורה כשהאינדקס k הוא בסוף, כלומר הרשימה ממוינת ואז עוברים רק פעם אחת על על האיברים ואין ואין תחלופה בכלל.

by ליהי (guest), 10 Dec 2016 14:41
סעיף א
ליהי (guest) 10 Dec 2016 14:24
in discussion Fall 2016/7 / HW3 Q3 » סעיף א

צריך להחזיר את האיבר הראשון כביכול?

סעיף א by ליהי (guest), 10 Dec 2016 14:24

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

O(2+n) = O(n)
O(n+n2) = O(n2)

אבל מה קורה כשמדובר בפונקציה אקספוננציאלית? האם גם אז תקפים הכללים ל"השמטה" של החזקה הגבוהה ביותר, כפי שהודגם בכיתה? לדוגמא:

1. O(2n + n7) =?= O(2n)
2. O(n*2n+2 + n5) =?= O(n*2n) =???= O(2n)

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

2. בשיוויון הראשון למעשה מבוצעת אותה פעולה כמו ב(1). אבל בשיוויון השני =???= השמטתי את n. כאן אני פחות בטוח - הרי אנחנו שומרים על logn בביטוי O(nlogn) - וזאת למרות שברור שגידול ליניארי כמו n גדול משמעותית מגידול לוגריתמי. הרי מה שיש לנו פה הוא פונקציה של n עם מקדם logn - זהו זמן ריצה שהוא גבוה יותר מO(n) אבל עדיין נמוך מO(n2).

השאלה, אם כן, האם ראוי לא לצמצם את הביטוי n*2n? ולראות בו בעצם פונקציה של 2n עם מקדם קטנטן של n?

קיצור נוטציות באו גדול וחסמים הדוקים by Yaniv Hassidim No life only CS (guest), 09 Dec 2016 23:28

היי,

בשאלה 5 לא נכתב מה יש לעשות במקרה בו הקלט מכיל tuple שבו a1=a2 וגם b1=b2.
האם משמעות הדבר היא כי קלט תקין לא יכיל צירוף מסוג זה?

תודה!

התייחסות למקרה בו b1=b2 by אלון (guest), 09 Dec 2016 23:20
a-b (guest) 09 Dec 2016 16:42
in discussion Fall 2016/7 / HW3 Q2 » שאלה 2 סעיף ב

תשמע, הפונקציה היא מהחיוביים לשלמים. אז רציפה היא לא.

אבל היא מונוטונית אז אסימפטוטות גם לא יהיו לך.

אקיצר, הכל בסדר :)

ואל תחלק ב-0, אין סיבה

by a-b (guest), 09 Dec 2016 16:42
שאלה 2 סעיף ב
ran (guest) 09 Dec 2016 13:49
in discussion Fall 2016/7 / HW3 Q2 » שאלה 2 סעיף ב

היי. האם אפשר להניח שהפונקציה הנקלטת היא רציפה? למשל, אם יש אסימפטוטות אנכיות כך אין חשש לחלק באפס..

תודה :)

שאלה 2 סעיף ב by ran (guest), 09 Dec 2016 13:49

יישר את הטקסט לימין.
ראה http://tau-cs1001-py.wikidot.com/forum/t-2016072/unique-pairs

Re: שאלה 5 by Amir GiladAmir Gilad, 09 Dec 2016 06:12
שאלה 5
Dan Tavori (guest) 08 Dec 2016 22:42
in discussion Fall 2016/7 / General Forum » שאלה 5

אהלן,
שאלה 5 בתרגיל האחרון: האם אני יכול לצאת מנקודת הנחה שלא קיימים שני טאפלים זהים בקלט? ובמידה ויהיו, האם מותר לי לאחד אותם?

שאלה 5 by Dan Tavori (guest), 08 Dec 2016 22:42
Re: שאלה ב5
Yuval WeissYuval Weiss 08 Dec 2016 21:41
in discussion Fall 2016/7 / HW3 Q5 » שאלה ב5

תיקון לשאלה:
האם פונקציה בסיבוכיות זמן של אן כפול קבוע מסוים, בכל במקרים, ולא רק במקרה הגרוע, מתאימה לשאלה זו?
תודה רבה!

Re: שאלה ב5 by Yuval WeissYuval Weiss, 08 Dec 2016 21:41
שאלה ב5
יובל וייס (guest) 08 Dec 2016 21:37
in discussion Fall 2016/7 / HW3 Q5 » שאלה ב5

האם פונקציה בסיבוכיות זמן של (O(n (בנוסף, יש קבוע כפול הסיבוכיות אך זה עדיין(O(n) בכל המקרים(לא רק במקרה הגרוע) מתאימה לשאלה זו?
תודה רבה!

שאלה ב5 by יובל וייס (guest), 08 Dec 2016 21:37
רועי סיני (guest) 08 Dec 2016 20:23
in discussion Fall 2016/7 / HW3 Q4 » סיבוכיות זיכרון

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

by רועי סיני (guest), 08 Dec 2016 20:23

ישר את הטקסט לימין בבקשה.

כאשר מחשבים סיבוכיות זיכרון, האם מתייחסים רק למספר המשתנים או גם לגודלם?

כלומר, האם סיבוכיות הזיכרון של הפעולה i = 5 קטנה או שווה לסיבוכיות הזיכרון שללסיבוכיות הזיכרון של הפעולה i = 500?

תודה :)

סיבוכיות זיכרון by Raz (guest), 08 Dec 2016 11:49

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

?איפה ההערות לשיעורי הבית by רועי סיני (guest), 08 Dec 2016 11:41

כפי שכתוב בתרגיל: בשאלה זו הניחו כי סיבוכיות הזמן עבור הפעלת f על קלט כלשהו היא O(1).

Re: סעיף א -2 by Amir GiladAmir Gilad, 07 Dec 2016 07:43

הכוונה היא כתיבה תמציתית. אם אין לך ברירה אלא לחרוג מ-2 שורות, נסה לחרוג בכמה שפחות.
כמו שכתוב בסעיף, ההוכחות אמורות להיות פשוטות.

ניתן להניח שהרשימה אינה ריקה

סעיף א -2
רון (guest) 06 Dec 2016 16:17
in discussion Fall 2016/7 / HW3 Q2 » סעיף א -2

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

סעיף א -2 by רון (guest), 06 Dec 2016 16:17

בשאלה 1א כתוב להוכיח בלא יותר מ-2 שורות.
האם באמת אסור להוכיח ביותר מ-2 שורות או שגם הוכחה באורך 3 או 4 שורות תתקבל?

אורך ההוכחה בשאלה 1א by הראל (guest), 06 Dec 2016 14:26
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License