שאלה בקשר לסיבוכיות

[snaidis]

שאלה בקשר לסיבוכיות

שלום, אם יש לי לולאה מקוננת. החיצונית זה מ 1 עד K הפנימית זה מ 1 עד N מהי הסיבוכיות של התוכנית?

 

[אמיר ל]

סיבוכיות זמן ריבועית...

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

O*O=O(n^2)​

מקווה שהבנת, אמיר.

 

[snaidis]

אה אוקי הבנתי תודה

 

[ahab]

פספסתי משהו?

מדובר בלולאה שמבצעת N איטרציות המוכלת בתוך לולאה שמבצעת K איטרציות. אלא אם כן נאמר משהו אודות K או N, סיבוכיות הזמן של זה היא

O(N*K)​

 

[אמיר ל]

כל לולאה שרצה מס' קבוע של פעמים

בתנאי, שהוא לא מספר, כמובן, כי אז אין רגישות לקלט, יש לה סיבוכיות זמן של O, ולא חשוב מה השם של הקבוע. הכוונה, שהרגישות היא לקלט. אם היא הקלט, k במקרה הזה, או n במקרה כללי, יגדל ב-1, מס' האיטרציות יגדל ב-1. לכן זמן הריצה של כל אחת מהלולאות, בפני עצמה, הוא O(n(, והסיבוכיות היא לינארית (גודלת בקו ישר). כיוון שהלולאה השנייה מקוננת בראשונה, במקרה הגרוע ביותר היא תרוץ N פעמים עבור N הפעמים שרצה הראשונה, ולכן סדר הגודל של סיבוכיות זמן הריצה של התוכנית הוא N בריבוע. אם נתרגם את הקבועים למספרים, לדוגמה k=2ו-n=10, הרי שהלולאה הפנימית רצה 10 פעמים עבור כל k, שעוצר ב-2, ולכן 10*10=20. כשמתרגמים את זה לקבועים, סיבוכיות זמן הריצה היא לינארית.

 

[אמיר ל]

*תיקוןנים: 10+10 וסיבוכיות ריבועית.

 

[ron369]

לא, אתה כנראה מתבלבל

אם יש לך שתי לולאות, אחת בתוך השניה (דביר לנצברג קרא לזה "דולאה" (du-la-a)

), החלק שבתוכן ירוץ NK פעמים. אם אחד מהם קבוע, אז זה באמת יהיה לינארי בשני. אם שניהם לא קבועים, למה שזה יהיה כך? למשל, נניח שיש לך לולאה כזו: for i=1 to N for j=1 to lgN do bla אז bla ייעשה N^2 או NlgN פעמים לכל היותר? (או שלא הבנתי אותך נכון?)

 

[אמיר ל]

אתה צודק. יחד עם זאת, אני מניח

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

 

[vinney]

קבוע הוא קבוע הוא קבוע

קבוע זה O של 1 תמיד. גם אם הקבוע ממש גדול, גם אם הקבוע לא ידוע, כל עוד זה קבוע (ומהשאלה הזאת לא נתון שK או N הם קלט, אז אפשר להגיד שזה קבוע) - זה תמיד O של 1. אם כך יש לך לולאה שרצה בO של 1 בתוך לולאה שרצה בO של 1 סה"כ זה O של 1. אם נשלים את השאלה למשהו יותר הגיוני, זה כנראה יהיה באמת O של K*N, כשK UוN זה שני קלטים בלתי תלויים (או לפי התלות, אם K וN זה גדלים של קלטים תלויים).

 

[snaidis]

לא זה לא קבועים

מצטער שכתבתי באותיות גדולות אז הסיבוכיות היא o(N*K)?

 

[snaidis]

את האמת...

חשבתי על זה לפני אבל לא הייתי בטוח שזה אפשרי לכתוב ככה. כי תמיד מזכירים סיבוכיות של N בריבוע ו N ו מעריכי. אז חשבתי שזה משהו לא אפשרי. טוב, תודה לכולכם שעזרתם.