שיחה:88-280 מבני נתונים ואלגוריתמים: הבדלים בין גרסאות בדף
| שורה 32: | שורה 32: | ||
x^8 = x^4*x^4 = x^2*x^2 * x^2*x^2 = ... | x^8 = x^4*x^4 = x^2*x^2 * x^2*x^2 = ... | ||
כלומר כל פעם קוראים לפונקציית חזקה עם בלוק קטן יותר. לדעתי זה אמור להקטין. סלבה. | כלומר כל פעם קוראים לפונקציית חזקה עם בלוק קטן יותר. לדעתי זה אמור להקטין. סלבה. | ||
אבל מה עושים עם מה שנשאר? נגיד- x^116=x^64*x^50. מה עושים עם הx^50? אחרת, זה יוצא שרצים על הרבה.. | |||
גרסה מ־16:15, 10 בנובמבר 2011
הוספת שאלה חדשה
הוסף שאלה חדשה (רשום כותרת לשאלה, רשום את תוכן השאלה ולחץ על שמירה למטה מימין לסיום).
-עזרה על עיצוב הטקסט וכתיב מתמטי תוכלו למצוא כאן
אם אתם רוצים לשאול שאלה עליכם ליצור חשבון משתמש באתר.
שאלות
תרגיל 1
שאלה 4 סעיף 3, יש שיטה פרט לאינטרציות עבור שני גורמים בתוך רקורסיה? כי לא ברור לי איך להציג שלב סופי? עבור איזה k ומה הוא הסוף במקרה זה?
- זכור שאתה צריך רק לתת [math]\displaystyle{ \Theta }[/math] של התשובה. מספיק למצוא חסם תחתון וחסם עליון. --אוריה 15:54, 3 בנובמבר 2011 (IST)
בסעיף 2 תשובה לפי אינטרציות ולפי משפט master שונות מדי, האם יתכן דבר כזה?
- אם התשובות שקיבלת הן [math]\displaystyle{ \Theta }[/math] אחת של השנייה זה בסדר. אחרת כנראה יש לך טעות. --אוריה 15:54, 3 בנובמבר 2011 (IST)
שאלה 5
לא ברורה לי השאלה. אם כפל a ב-a
נחשב לפעולה, אז איך ניתן להפחית במספר פעולות.
בסופו של דבר אני עדיין אמור לכפול a בעצמו n פעמיים...
- רמז: מה אם n חזקה של 2? --אוריה 15:54, 3 בנובמבר 2011 (IST)
ומזה "סיבוכיות זיכרון" ?
- נגיע לזה בתרגול הקרוב. זו כמות התאים בזיכרון שהאלגוריתם צריך. --אוריה 15:54, 3 בנובמבר 2011 (IST)
שאלה 6 אסימפטותית?
- סיבוכיות זמן\זיכרון אסימפטוטית אומר [math]\displaystyle{ \Theta }[/math] של הזמן\זיכרון.
לגבי שאלה 5 לדעתי צריך לחשוב קיבוצית - נניח יש לך איקס בשמינית לחשב, ויש לך פונקציה של חזקה, אתה מכניס שלם חיובי, ומספר ומקבל חזרה את המספר בחזקה: x^8 = x^4*x^4 = x^2*x^2 * x^2*x^2 = ... כלומר כל פעם קוראים לפונקציית חזקה עם בלוק קטן יותר. לדעתי זה אמור להקטין. סלבה.
אבל מה עושים עם מה שנשאר? נגיד- x^116=x^64*x^50. מה עושים עם הx^50? אחרת, זה יוצא שרצים על הרבה..
שאלה 6
יכול להיות שיש טעות באלגוריתם? ז"א במקום for i = 2 to n-1: צריך להיות for i = 0 to n-1:
- אין טעות. אם יתחילו את הלולאות מ-0 האלגוריתם יעשה פעולה אחרת. --אוריה 15:54, 3 בנובמבר 2011 (IST)
בשאלה 2 הכוונה לפונקציות אי שליליות?
- כן. הכוונה היא לפונקציות אי שליליות.--אוריה 20:32, 6 בנובמבר 2011 (IST)
שאלה 5
אם בתוך האלגוריתם אני משתמש בערך של log(n האם זה נחשב לפעולה אחת?
- לצורך התרגיל, כן.--אוריה 20:32, 6 בנובמבר 2011 (IST)
מצאתי דרך שתפתור את הרקורסיה מהסוג של 4ג ממש ביעילות ולהלן הקישור לאלגוריתם זה. סלבה.