 נושא: שאלה על זמן ריצה של פונקציה
|
 
|
| כותב |
|
shlomiye
משתמש מתחיל
הצטרף / הצטרפה: 09 July 2011
משתמש: מנותק/ת
הודעות: 3
|
| נשלח בתאריך: 09 July 2011 בשעה 12:33 | | IP רשוּם
|
|
|
|
שלום,
מישהו יכול לעזור לי בתשובה תודה.
השאלה מצורפת:
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 09 July 2011 בשעה 22:19 | | IP רשוּם
|
|
|
|
אם התכוונת לשאלה 4 - התשובה היא ב'
הלולאה הראשית מתבצעת N+1 פעמים
הלולאה המשנית - לוקחת את המספר N ומחלקת אותו ב-2 כל עוד התוצאה גדולה מהמספר של הלולאה - (במקרה הקיצון מדובר פה בהגדרה של log(N) פעמים)
כלומר הסיבוכיות היא N * log(N)
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shlomiye
משתמש מתחיל
הצטרף / הצטרפה: 09 July 2011
משתמש: מנותק/ת
הודעות: 3
|
| נשלח בתאריך: 09 July 2011 בשעה 22:29 | | IP רשוּם
|
|
|
|
זה גם מה שאני חשבתי במבחן, אך המרצה פרסם תשובות ולפי דעתו זה סיבוכיות של N
אתה יכול לראות למה? או ששוווה לערער על שאלה זו?
תודה.
|
| חזרה לתחילת העמוד |
|
| |
shoshan
מנהל האתר
הצטרף / הצטרפה: 16 July 2005
מדינה: Israel
משתמש: מנותק/ת
הודעות: 4637
|
| נשלח בתאריך: 10 July 2011 בשעה 00:49 | | IP רשוּם
|
|
|
|
היי, בדקתי ע"י כתיבת תכנית קטנה בפייתון והמרצה צודק לגמרי.
אין לי כוח להעלות גרף מאקסל אבל הגרף לינארי לחלוטין כאשר הסדר גודל המדויק של מספר ההדפסות הוא 2N.
מספר ההדפסות בלולאה הפנימית
אם נחשוב לעומק על מספר ההדפסות הוא יהיה (לדוגמא עבור N=100 יודפס 100 פעמים 100, עבור כל המספרים, 50 פעם 50, עבור כל המספרים הקטנים מ-50, 25 פעם 25, עבור על המספרים הקטנים מ-25, 12 פעם 12, עבור כל המספרים הקטנים מ-12 וכו'...):
1N + 0.5N + 0.25N + 0.125N + ... - ככה N פעמים ... ועוד 1 (שזה כמות ההדפסות של המספר 0)
ניתן לחשב לפי סכום סדרה הנדסית
הסכום מתכנס ל-2
__________________
עד מתי רשעים יעלוזו?
עַל כֵּן אֶמְאַס וְנִחַמְתִּי עַל עָפָר וָאֵפֶר.
|
| חזרה לתחילת העמוד |
|
| |
shlomiye
משתמש מתחיל
הצטרף / הצטרפה: 09 July 2011
משתמש: מנותק/ת
הודעות: 3
|
| נשלח בתאריך: 10 July 2011 בשעה 06:31 | | IP רשוּם
|
|
|
|
תודה.
|
| חזרה לתחילת העמוד |
|
| |
|
|
אם ברצונך להגיב לנושא זה עליך קודם להתחבר
אם אינך רשום/ה כבר עליך להרשם
|
|
אינך יכול/ה לשלוח נושאים חדשים בפורום זה
אינך יכול/ה להגיב לנושאים בפורום זה
אינך יכול/ה למחוק את הודעותיך ותגוביך בפורום זה
אינך יכול/ה לערוך את הודעותיך ותגובותיך בפורום זה
אינך יכול/ה לצור סקרים בפורום זה
אינך יכול/ה להצביע בסקרים בפורום זה
|
נושאים פעילים
רשימת משתמשים
חיפוש
עזרה
הרשמה
התחברות
UnderWarrior Forums : 
מדעי המחשב
