ישנם שתי תוכניות (3 לולאות בכל תוכנית) אני רוצה לדעת את הסיבוכיות הריצה של

הלולאות כתלות בN...

תודה

[attachment deleted by admin]

זה תלוי בלולאות , ואיך מחשבים את ה אינדקס הבא שלהם . אם הם לולאות FOR פשוטות אז הסיבוכיות יכולה להיות N^3 אם הם אחד בתוך השני. הם יכולים להיות גם N^2 +N שזה פשוט N^2 זה יכול להיות גם O של 3N שהוא O של N . יש קורס שלקחתי שנקרא analysis of algorithm ששם למדו אותנו את כל זה (למדתי בארה"ב). יש גם זמן ריצה של best case ו worst case ולרוב מסתכלים על average case . לכל אחד מהם יש אות.

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

אני מדבר על המקרה הממוצע...

הבעיה שלי היא חישוב הסיבוכיות של כל לולאה...

לא אכפת לי מערכו של sum אם לזה התכוונת...

הקטע שאני יודע רק את הסיבוכיות של שני הלולאות הראשונות שבני הסעיפים שהוא N....

תודה על העזרה...

יכול להיות שהלולאות לא מכסות את כל אינדקסים ...יכול שאתה סורק פחות ...

אתה חייב להסביר מה צורת הלולאות

1) כל אחד עושה לולאה משלה 3N שזה N

2) לולאה בתוך לולאה N^2

3) לולאה בתוך לולאה בתוך לולאה N^3

כל סעיף(ויש שניים כאלו) הם שלוש לולאות מכוננות...

אני יודע את הכלל הזה אם יש לך לולאה בתוך ללואה אז זה N^2 הבעיה שהלולאה

השנייה רצה עד i*i ולא עד N ובלולאה השלישית היא מחלקת ב10 כל פעם...

תעתיק לפה את התוכניות הללו.

הרבה יותר קל לחשב זמן ריהצ של אלגוריתם כשבאמת רואים את האלגוריתם!

יש קובץ בהודעת פתיחה של התראד אבל כרצונך...

//-------First mini program

sum=0;

for(i=0;i<N;i++)

for(j=0;j<i*i;j++)

for(k=j;k>0;k/=10)

sum++;

_____________________________________

//Second mini program

sum=0;

for(i=0;i<N;i++)

for(j=0;j<i*i*i;j++)

for(k=j;k>=0;k--)

sum++;

תוכנית ראשונה

לופ ראשון

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

יצא לי הסעיף הראשון n^3logn ולכן הסיבוכיות היא n^3

ובסעיף השני יצא n ^7

לא יודע אם אפשר להעיף את ה 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 .

כדאי לך לשים לב לדברים האילו במבחן ולא לעשות חפיף כמוני

צודק... זמן ריצה של א הוא 2^(n^3*(log n ה2 לא עובר ימינה כי הבסיס שלך הוא 10 ולא n....

לגבי השני אני עדיין לא הבנתי איך הגעת לn^13???(ועוד קבלתי n^7.... :-X)

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

 logb (n^k) = k*logb (n) 

b הוא הבסיס . בגלל זה לקחת לוג של כל חזקה הופך אותה לקבוע שמופל בלוג שבקיצור עף מחישוב הסיבוכיות.

עוד אחד שימושי זה

 logb x = log(x)/log(b) 

זה חוק שינוי בסיסים בlog

...//Second mini program
sum=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 (הציון הגבוה ביותר האפשרי) בלי לקחת את המבחן הסופי אבל ההשיגים שלי בעבר לא צריכים להעיד על השיגים שלי בהווה בנושא. כדאי לך להתיעץ עם סטודנט אחר שאולי לקח קורס כזה בשנה שעברה אולי המידע הזה טרי אצלו בראש.

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

אם לולאה רצה עד N אז הסיבוכיות שלה היא N

אם לולאה רצה עד N^2 אז הסיבוכיות שלה אמורה להיות N^2 ולא חשוב אם היא רשומה ב 2 לולאות או לא, זו הסיבוכיות שלה.

אז לפי החישוב שלי התוכנית הראשונה אמורה להיות N^5

והשניה N^10

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

עריכה:

רק עכשיו ראיתי את ה חילוק ב 10 התשובה שלך נראית לי נכונה N^3ln(N^2) וזה בעצם N^2lnN

הבעיה שאין מתרגל אם היה(אחרי המבחן הסופי אולי יהיה בשנה הבאה....חחחח)

התכוונת לlog n ולא לln בסיס של e והlog בסיס של 10

צודק