שאלה לגבי סיבוכיות זמן ריצה

[snaidis]

שאלה לגבי סיבוכיות זמן ריצה

אם יש לי תוכנית לדוגמא שיש שם דבר כזה: for(i=0;i<10;i++) ddd for(j=0;j<10;j++) ...... ddd for(i=0;i<10;i++) ddd for(j=0;j<10;j++) ...... ddd אז מהי הסיבוכיות זמן ריצה של התוכנית? כאילו הבנתי שהחלק הראשון זה O(N^2) אבל אם יש לי שני לולאות אז מה הופכת להיות הסיבוכיות? נ.ב ddd זה רק ליישור. תודה לעונים

 

[טיורינג]

דבר ראשון

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

 

[snaidis]

רגע...רגע...

אבל אם יש לי לולאה בתוך לולאה שכל אחת רצה מ1 עד 1000000 .ולולאה בתוך לולאה שכל אחת רצה מ 1 עד N והקלט של Nיכול להיות מקסימום מיליון. אז הסיבוכיות של המקרה הראשו תהיהO(1) ושל השני הסיבוכיות תהיה:O(N^2)?

 

[טיורינג]

יש הגדרה קצת יותר הדוקה

לגבי סיבוכיות, כי המקרה שציינת אכן בעייתי עם קבועים מאוד גדולים. אבל, לפחות לאקדמיה כל קבוע מוזנח (גם אם הוא מאוד גדול, ובתנאי שאת לא לומדת קורסים מתקדמים יותר). את הסיבוכיות מחשבים כסכום כולל של כל הקוד, והגדול מנצח. כלומר אם היתה לך לולאה שרצה 10 פעמים, ואחריה לולאה כפולה שרצה N^2 פעמים, ואחריה עוד לולאה שרצה N פעמים אז סה"כ הסיבוכיות היא 10 + N^2 + N = O(N^2) כלומר רק הלולאה הכפולה באמת משנה לסיבוכיות, כל השאר זניחים ביחס אליה.

 

[snaidis]

OK אבל למה אתה חושב שאני אישה???

 

[טיורינג]

../images/Emo52.gif

אין לי מושג למה...