מנסה להבין סיבוכיות מהי
- פותח הנושא assaf990
- פורסם בתאריך
סיבוכיות על קצה המזלג
בדר"כ מודדים את היעילות של אלגוריתם (בוא נדבר כרגע על יעילות זמן) לפי "כמה פעולות בסיסיות הוא מבצע כפונקציה של אורך הקלט". כלומר, מה שבעיקר מעניין אותנו זה לא "האלגוריתם רץ 5 שניות" כי זה חסר משמעות, אלא כמה האלגוריתם רגיש לשינויים בקלט, או במילים אחרות, אם נגדיל את הקלט ביחס מסויים, איך יגדל זמן הריצה של האלגוריתם? אם האלגוריתם לא תלוי בכלל בקלט (למשל, לולאה שרצה 10 פעמים) אז האלגוריתם בכלל לא רגיש לקלט, הוא אפילו אדיש אליו, ולכן הסיבוכיות שלו היא אושן 1 (מצטער, ויני, פעם אחרונה ודי!) O(1) כמובן. אם האלגוריתם שלך קולט מספר N ואז יש לולאה שרצה N פעמים אז הסיבוכיות היא O(N) - כלומר האלגוריתם רגיש בצורה ליניארית לקלט - ברור לך שככל שתגדיל את N ככה זמן הריצה יגדל בצורה ליניארית. ויש עוד כל מיני. ולעניין ה-O, זה כבר סיפור אחר, אין לי כוח לכתוב כרגע, אבל תגיד אם זה עוזר בכלל...
בדר"כ מודדים את היעילות של אלגוריתם (בוא נדבר כרגע על יעילות זמן) לפי "כמה פעולות בסיסיות הוא מבצע כפונקציה של אורך הקלט". כלומר, מה שבעיקר מעניין אותנו זה לא "האלגוריתם רץ 5 שניות" כי זה חסר משמעות, אלא כמה האלגוריתם רגיש לשינויים בקלט, או במילים אחרות, אם נגדיל את הקלט ביחס מסויים, איך יגדל זמן הריצה של האלגוריתם? אם האלגוריתם לא תלוי בכלל בקלט (למשל, לולאה שרצה 10 פעמים) אז האלגוריתם בכלל לא רגיש לקלט, הוא אפילו אדיש אליו, ולכן הסיבוכיות שלו היא אושן 1 (מצטער, ויני, פעם אחרונה ודי!) O(1) כמובן. אם האלגוריתם שלך קולט מספר N ואז יש לולאה שרצה N פעמים אז הסיבוכיות היא O(N) - כלומר האלגוריתם רגיש בצורה ליניארית לקלט - ברור לך שככל שתגדיל את N ככה זמן הריצה יגדל בצורה ליניארית. ויש עוד כל מיני. ולעניין ה-O, זה כבר סיפור אחר, אין לי כוח לכתוב כרגע, אבל תגיד אם זה עוזר בכלל...
אממממ,
פעולה היא O(1) zzz אם היא לוקחת מספר צעדים קבוע (כמו לסכום 1+1 או כמו לסכום 1+1+1+1). אם אלגוריתם מבצע n פעולות שכל אחת מהן לוקחת זמן O(1) zzz אז סך כל זמן הריצה יהיה O
zzz. אם אלגוריתם אחר מבצע n פעולות שכל אחת מהן לוקחת זמן O zzz אז זמן הריצה יהיה O(n^2) zzz. אם אלגוריתם אחר מבצע n^2 פעולות שכל אחת מהן לוקחת זמן ריצה של O(logn) zzz אז זמן הריצה יהיה O(n^2 *logn) zzz. זה עוזר במשהו? יש לך דוגמא ספציפית שאתה מתקשה איתה?
פעולה היא O(1) zzz אם היא לוקחת מספר צעדים קבוע (כמו לסכום 1+1 או כמו לסכום 1+1+1+1). אם אלגוריתם מבצע n פעולות שכל אחת מהן לוקחת זמן O(1) zzz אז סך כל זמן הריצה יהיה O
zzz. אם אלגוריתם אחר מבצע n פעולות שכל אחת מהן לוקחת זמן O zzz אז זמן הריצה יהיה O(n^2) zzz. אם אלגוריתם אחר מבצע n^2 פעולות שכל אחת מהן לוקחת זמן ריצה של O(logn) zzz אז זמן הריצה יהיה O(n^2 *logn) zzz. זה עוזר במשהו? יש לך דוגמא ספציפית שאתה מתקשה איתה?Copyright©1996-2021,Tapuz Media Ltd. Forum software by XenForo® © 2010-2020 XenForo Ltd.