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

[אש קודש!]

אפשר לפנות אליך גם אם שאלות?

תכתבי כאן, אני מאמינה שמבין הבנות הללו תהייה מישהי שתענה בשמחה...

 

[אנונימיתתתת]

אתן יודעות אם במבחן אני צריכה להתחשב בסיבוכיות מקום??

אפילו לא למדנו את זה

 

[סוכריה בלי מקל]

אתן יודעות אם במבחן אני צריכה להתחשב בסיבוכיות מקום??

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

 

[תותית י.]

אתן יודעות אם במבחן אני צריכה להתחשב בסיבוכיות מקום??

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

 

[ias]

גם אם זה סיבוכיות מקום הזויה??
משהו כמו N מטריצות?
(אבל הסיבוכיות זמן ממש נורמלית...)

 

[סוכריה בלי מקל]

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

 

[אנונימיתתתת]

בבעיות נסיגה כאשר אני פותרת בעזרת עץ בינארי לדוגמא את השאלה הזו:
T = T(n/2) + T(n/7) + n ואז עשיתי מה שכתוב בצילום מסך והלאה איך ממשיכים?

 

[סוכריה בלי מקל]

@אנונימיתתת
דבר ראשון- את מכירה את נוסחת הנסיגה? גם יעזור לך.
שנית, שימי לב שאת מגיעה בכל שלב בעץ לN חלקי משהו, וסה"כ בסיבוכיות זה N. (מסתכלים בכל שורה שבה יש חלוקה- על כל הענפים שנמצאים בשורה הזו. כמה בסה"כ היה כאן בשורה?)
עכשיו מה שנותר לך זה לזהות כמה פעמים את מבצעת את הN הזה. (n? log n? nlogn? וכו'... קל מאד לזהות. תחשבי כמה פעמים את צריכה לבצע התחלקות של ענפים- כלומר, כמה פעמים הפעולה עובדת ומבצעת לך משהו בגודל n, כמו שהסברתי. האם בסך הכל זה יקרה עד שנגיע ל2 בחזקת משהו- שירכיב את המספר אליו את חותרת להגיע- ואז זה כמובן logn? וכדומה).
(מנחשת שזה תרגיל שעוסק בבניית מערכים מחדש והרכבה, סוג של מיון כנראה. נכון?)

 

[צניחה חופשית]

גם אם זה סיבוכיות מקום הזויה??
משהו כמו N מטריצות?
(אבל הסיבוכיות זמן ממש נורמלית...)

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

 

[אנונימיתתתת]

דבר ראשון תודה על היחס דבר שני זה בדיוק מה שלא הצלחתי להגיע בפעם הראשונה:=n
השניה=n/2+n/7
השלישית=n/14+n/4+n/14+n/49
ואז מה עושים או שבכלל לא עשיתי טוב?! אין לי מושג...

 

[ias]

יש לי את התרגיל הזה:

אם יש למישהי כוח לפתור אותו ויצא לה סיבוכיות מקום יותר נורמלית אני אשמח!!

 

[סוכריה בלי מקל]

דבר ראשון תודה על היחס דבר שני זה בדיוק מה שלא הצלחתי להגיע בפעם הראשונה:=n
השניה=n/2+n/7
השלישית=n/14+n/4+n/14+n/49
ואז מה עושים או שבכלל לא עשיתי טוב?! אין לי מושג...

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

 

[ש.כ]

(O(n(n!), שהיא בעצם: O(nlogn), לפי חוקי סיבוכיות.

איך זה יכול להיות????

 

[סוכריה בלי מקל]

איך זה יכול להיות????

תראי שערכתי ותיקנתי...
בשעה הזאת הכל יכול להיות

 

[אש קודש!]

תראי שערכתי ותיקנתי...

אה, עכשיו הכול ברור .

 

[סוכריה בלי מקל]

אבל את באמת חושבת שהבנתי את פשר ה-O???

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

 

[פדאהל]

המראה. זו באמת בעיה!
מקסימום תיקראי לתיקיה 'חיימוש' עם 3 לבבות.
אבל התכוונתי לתיקיה בסרגל כלים!
צפה בקובץ המצורף 1411638

וואי איך עושים תיקייה בסרגל כלים?
אף פעם לא ניסיתי

 

[lea.dev.top]

משתדלת פעם בשבוע לפתור לפחות תרגיל אחד מליטקוד ברמת מדיום.

איפה אפשר ללמוד את הנושא?