Recent Forum Posts
From categories:
page 1123...next »
סעיף ב
יואל (guest) 30 Apr 2017 18:32
in discussion Spring 2017 / HW3 Q1 » סעיף ב

היי,

כשאני מחשב את הסיבוכיות של הפונקציות הנתונות, האם צריך לקחת בחשבון את הסיבוכיות של range בנפרד מ-extend? אם כן, האם להניח שהסיבוכיות היא או של אורך הרשימה הנוצרת?

תודה,

יואל

סעיף ב by יואל (guest), 30 Apr 2017 18:32

כן, הזכרנו בקצרה את המושג בכיתה, והסברנו שהוא מציין את כמות משאבי הזיכרון (בניגוד לזמן) שדורש אלגוריתם.
המושג נלמד בין השאר דרך תרגילי הבית.

הסדר לא בהכרח עולה ממש.

by Amir RubinsteinAmir Rubinstein, 30 Apr 2017 18:22
אורחת (guest) 30 Apr 2017 16:46
in discussion Spring 2017 / HW3 Q5 » סיבוכיות סעיף ג'

תודה רבה!

by אורחת (guest), 30 Apr 2017 16:46

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

by oren (guest), 30 Apr 2017 14:47
inbar (guest) 30 Apr 2017 12:47
in discussion Spring 2017 / HW3 Q3 » סעיף ג.3

ובעצם אותה השאלה תקפה גם לגבי ג.4- צריך לזהות את המגמה או לחפש נוסחה שמתארת את הקשר?

by inbar (guest), 30 Apr 2017 12:47
סעיף ג.3
inbar (guest) 30 Apr 2017 12:28
in discussion Spring 2017 / HW3 Q3 » סעיף ג.3

שלום,
רק לשם הבהרה- בסעיף ג.3 אנחנו אמורים לייצר נוסחה לחישוב קבוע הפרופורציה כתלות במימד? או להציג את קבוע הפרופורציה שמצאנו עבור כל מימד?

סעיף ג.3 by inbar (guest), 30 Apr 2017 12:28

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

אם לא נאמר אחרת תמיד מתייחסים בניתוח סיבוכיות למקרה הגרוע.

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

חמש שורות נשמע לי הרבה להוכחות מהסוג שנדרשתן אליהן. זה תלוי כמובן בגודל הפונט ובגבולות הדף.
האם מדובר בסעיף מסויים?

by Amir RubinsteinAmir Rubinstein, 30 Apr 2017 10:46

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

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

לגבי השאלה הראשונה, מה שכתבת הוא בגדול נכון, והנה הסבר מסודר:

סיבוכיות זמן היא מדד ליעילות האלגוריתמים שאנחנו מפתחים.
נהוג למדוד סיבוכיות במונחים של "O". חלק מהיתרונות בכך הוא שניתן אז להזניח קבועים מסויימים, למשל קבועים חיבוריים, כדוגמת (n+1 = O(n וכן קבועים כפליים, כדוגמת (2n = O(n.

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

לגבי השאלה השניה - כאשר מנתחים סיבוכיות של אלגוריתם צריך להסתכל על כל החלקים שלו. שורות קוד שאינן בתוך לולאות אמנם מתבצעות פעם אחת, אבל הן יכולות להיות בעלות סיבוכיות שאיננה קבועה. למשל, פקודת slicing, או קריאה לפונקציה. הפקודה (max(L למשל רצה בסיבוכיות (|O(|L.

Re: סיבוכיות by Amir RubinsteinAmir Rubinstein, 30 Apr 2017 10:37
לגבי סעיף ג'
noy (guest) 30 Apr 2017 08:57
in discussion Spring 2017 / HW3 Q5 » לגבי סעיף ג'

היי, בסעיף ג' (היעזרות שלא תלויה ב- k)
צריך עדיין לשמור על היתרון במהירות שנובעת מהעובדה שאנחנו יודעים שערך האיברים לא יכול לעבור את k?

תודה רבה

לגבי סעיף ג' by noy (guest), 30 Apr 2017 08:57
שאלה 6 א - ניסוח
inbar oz (guest) 30 Apr 2017 07:16
in discussion Spring 2017 / HW3 Q6 » שאלה 6 א - ניסוח

השאלה עצמה:
בהינתן שתי פונקציות (x(f1 ו- (x(f2 ,שתיהן גזירות )כלומר עומדות בתנאי הנדרש עבור שיטת ניוטון רפסון(,
נרצה למצוא ערך x בו הפונקציות נפגשות, כלומר (x(f2) == x(f1
שלימו בקובץ השלד את הפונקציה (f2, f1(equal המחזירה ערך x כזה, אם קיים. יש להשלים שתי שורות
בלבד. הפונקציה תקרא ל- NR

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

שאלה 6 א - ניסוח by inbar oz (guest), 30 Apr 2017 07:16

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

סיבוכיות סעיף ב' by may (guest), 29 Apr 2017 18:30
סיבוכיות סעיף ג'
אורחת (guest) 29 Apr 2017 16:10
in discussion Spring 2017 / HW3 Q5 » סיבוכיות סעיף ג'

היי, האם אפשר לממש פיתרון בסיבוכיות של n^2?
או שהכוונה היא לממש פיתרון יעיל יותר עבור ערכי קיי (לא יכולה לכתוב את האות באנגלית, הופך את הסדר..) קטנים כיוון שיש לנו מידע על הקלט?

סיבוכיות סעיף ג' by אורחת (guest), 29 Apr 2017 16:10

השאלה מתייחסת לתרגיל 3, טעיתי בפורום

by אני (guest), 29 Apr 2017 15:32
page 1123...next »
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License