פורסם 2007 במרץ 2318 שנים ישנם שתי תוכניות (3 לולאות בכל תוכנית) אני רוצה לדעת את הסיבוכיות הריצה של הלולאות כתלות בN...תודה[attachment deleted by admin]
פורסם 2007 במרץ 2418 שנים זה תלוי בלולאות , ואיך מחשבים את ה אינדקס הבא שלהם . אם הם לולאות FOR פשוטות אז הסיבוכיות יכולה להיות N^3 אם הם אחד בתוך השני. הם יכולים להיות גם N^2 +N שזה פשוט N^2 זה יכול להיות גם O של 3N שהוא O של N . יש קורס שלקחתי שנקרא analysis of algorithm ששם למדו אותנו את כל זה (למדתי בארה"ב). יש גם זמן ריצה של best case ו worst case ולרוב מסתכלים על average case . לכל אחד מהם יש אות. יש גם מקרים שמחשבים את ה אינדקס ולא עושים לו ++ או -- והכל תלוי איך עושים את זה ומה התנאי יציאה מהלופ.
פורסם 2007 במרץ 2418 שנים מחבר אני מדבר על המקרה הממוצע...הבעיה שלי היא חישוב הסיבוכיות של כל לולאה...לא אכפת לי מערכו של sum אם לזה התכוונת...הקטע שאני יודע רק את הסיבוכיות של שני הלולאות הראשונות שבני הסעיפים שהוא N....תודה על העזרה...
פורסם 2007 במרץ 2418 שנים יכול להיות שהלולאות לא מכסות את כל אינדקסים ...יכול שאתה סורק פחות ...אתה חייב להסביר מה צורת הלולאות 1) כל אחד עושה לולאה משלה 3N שזה N2) לולאה בתוך לולאה N^23) לולאה בתוך לולאה בתוך לולאה N^3
פורסם 2007 במרץ 2418 שנים מחבר כל סעיף(ויש שניים כאלו) הם שלוש לולאות מכוננות...אני יודע את הכלל הזה אם יש לך לולאה בתוך ללואה אז זה N^2 הבעיה שהלולאההשנייה רצה עד i*i ולא עד N ובלולאה השלישית היא מחלקת ב10 כל פעם...
פורסם 2007 במרץ 2418 שנים תעתיק לפה את התוכניות הללו.הרבה יותר קל לחשב זמן ריהצ של אלגוריתם כשבאמת רואים את האלגוריתם!
פורסם 2007 במרץ 2418 שנים מחבר יש קובץ בהודעת פתיחה של התראד אבל כרצונך...//-------First mini programsum=0;for(i=0;i<N;i++) for(j=0;j<i*i;j++) for(k=j;k>0;k/=10) sum++;_____________________________________//Second mini programsum=0;for(i=0;i<N;i++) for(j=0;j<i*i*i;j++) for(k=j;k>=0;k--) sum++;
פורסם 2007 במרץ 2518 שנים תוכנית ראשונהלופ ראשוןN לופ שני1^2 + 2^2 +3^2... N^2צריך את הנוסחה שאומרת מה ההתכנסות של ה (sum (i^2 בין 0 ל N מתכנס ל...הלופ האחרות תלוי ב LOG10 של j אז זה log10 של הנוסחה של הלופ שניאת השני אתה כבר יכול לפטור בעצמך. הלינק הזה יעזור לך http://library.thinkquest.org/20991/gather/formula/data/209.html
פורסם 2007 במרץ 2518 שנים מחבר יצא לי הסעיף הראשון n^3logn ולכן הסיבוכיות היא n^3 ובסעיף השני יצא n ^7
פורסם 2007 במרץ 2518 שנים לא יודע אם אפשר להעיף את ה log n עדיף להשעיר אבל אני לא בטוח אבל ה n^3 log n זה נכון . ( n^3 * log n^2 = 2*n^3log n ) תיקון טעות : אני חשבתי שהשני הוא N^9 אבל טעיתי זה N*N^4*N^4*N^4 שיוצא סך הכל N^13 הסיבה לכך שהלופ הראשון הוא N השני מתכנס ל N^4 והשלישי הוא סכום מספרים עוקבים שהנוסחה שלו היא (N+1)*N/2 ובגלל שה N של ה לופ השלישי הוא N^4 אז יוצא שהוא מתכנס ל N^8 . כדאי לך לשים לב לדברים האילו במבחן ולא לעשות חפיף כמוני
פורסם 2007 במרץ 2618 שנים מחבר צודק... זמן ריצה של א הוא 2^(n^3*(log n ה2 לא עובר ימינה כי הבסיס שלך הוא 10 ולא n....לגבי השני אני עדיין לא הבנתי איך הגעת לn^13???(ועוד קבלתי n^7.... :-X)
פורסם 2007 במרץ 2618 שנים עריכה : בדיוק ראיתי שיש לך טעות בענין הלוג . יש חוקים לlog מכל בסיס שכדאי לזכור logb (n^k) = k*logb (n) b הוא הבסיס . בגלל זה לקחת לוג של כל חזקה הופך אותה לקבוע שמופל בלוג שבקיצור עף מחישוב הסיבוכיות.עוד אחד שימושי זה logb x = log(x)/log(b) זה חוק שינוי בסיסים בlog...//Second mini programsum=0;for(i=0;i<N;i++) for(j=0;j<i*i*i;j++) for(k=j;k>=0;k--) sum++;לופ ראשון זה ברור N בלופ השני שעל פי הנוסחה :the sum of cubes of first 'n' natural no`s-1^3+2^3+3^3+4^3+......+n^3=(n^2 * (n+1)^2)/4 מתכנס ל N^4 כי כל i הוא רץ i^3 פעמים זה יוצא סכום של חזקות של 3הלופ האחרון הוא גם סכום כי הוא רץ מהערך של j עד 0 וזה אומר שהוא הסכום של המספרים בין 1 ל m (בכוונה בחרתי אות אחרת ) שמתכנס ל m^2 ( אם לוקחים זוגות של מספרים מקבלים תמיד את אותו ערך אז מחשבים את הערך הזה m+1 ואז מכפילים בחצי m ) . בגלל שאנחנו בלופ השלישי הm הוא בעצם n^4 . אז יוצא n*n^4*n^4^2 = n^13 . האמת שאני כבר מבולבל ולא בטוח אם אני צודק ניסיתי לפתוח ספר לראות דוגמה אבל לא מצאתי. יכול להיות שזה רק N^8 בגלל הלופ האחרון אני כבר לא זוכר את כל הדברים האילו שלמדתי לפני 12 שנים. מה שאני כן זוכר שקיבלתי A (הציון הגבוה ביותר האפשרי) בלי לקחת את המבחן הסופי אבל ההשיגים שלי בעבר לא צריכים להעיד על השיגים שלי בהווה בנושא. כדאי לך להתיעץ עם סטודנט אחר שאולי לקח קורס כזה בשנה שעברה אולי המידע הזה טרי אצלו בראש.
פורסם 2007 במרץ 2618 שנים אני הראשון להודות שאני לא מומחה גדול בזה אבל נראה לי שיש לכם טעות.אם לולאה רצה עד N אז הסיבוכיות שלה היא Nאם לולאה רצה עד N^2 אז הסיבוכיות שלה אמורה להיות N^2 ולא חשוב אם היא רשומה ב 2 לולאות או לא, זו הסיבוכיות שלה.אז לפי החישוב שלי התוכנית הראשונה אמורה להיות N^5והשניה N^10למה שלא תיפול עם השאלה הזו על איזה מתרגל? יחסוך לך זמן וויכוחים פה בפורום.עריכה:רק עכשיו ראיתי את ה חילוק ב 10 התשובה שלך נראית לי נכונה N^3ln(N^2) וזה בעצם N^2lnN
פורסם 2007 במרץ 2618 שנים מחבר הבעיה שאין מתרגל אם היה(אחרי המבחן הסופי אולי יהיה בשנה הבאה....חחחח)התכוונת לlog n ולא לln בסיס של e והlog בסיס של 10
ארכיון
דיון זה הועבר לארכיון ולא ניתן להוסיף בו תגובות חדשות.