אני מנסה ללמוד את עניין הסיבוכיות (מבנה נתונים א), הייתי בהרצאה, קראתי כל מיני סיכומי הרצאות קצרצרים אך לא הבנתי.

האם יש מקור שמפרט על העניין הזה יותר?

לפחות ברמה ראשונית כלשהי אני רוצה להבין.

(מתי פעולה היא אושן 1 מתי היא אושן N)

אם אתה מבצע כל הזמן מספר פעולות קבוע - O(1)

אם אתה מבצע זמן פעולות שהוא בערך N - O(N)

אם אתה מבצע מספר פעולות שהוא בערך N^2 - O(N^2)

אותו דבר עבור logN והבדלים בסדרי גודל.

אם יש לך נגיד 3*n פעולות אז זה o(n) מכיוון שמספר קבוע לא משפיע.

לפי ההגדרה זה:

o(a)אם"ם

f<c*a כאשר C מספר קבוע, וF זה זמן הריצה בפועל(אני לא זוכר כל כך את ההגדרה אך היא משהו בסגנון)

ואומרים O(N) או של אנ וזה לא האות האנגלית או אלא האות היוונית אוקימורון(אך קוראים כO).

טוב אז כחה

בעיקרון זה אומר כמה פעמיפים פעולה חוזרת על עצמה

אז אם יש לך לולאה זה נחשב סיבוכיות N

ואם יש לולאה בתוך לולאה זה N^2

ויש הרבה סוגים של סיבוכיות כמו

1

LOGN (בבסיס 2)

N

N^2

ועוד כמה

טוב אז כחה

בעיקרון זה אומר כמה פעמיפים פעולה חוזרת על עצמה

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

ויש הרבה סוגים של סיבוכיות כמו

1

LOGN (בבסיס 2)

N

N^2

ועוד כמה

מה הסיבוכיות של זה?

for(int i=0;i<100;i++)

{

printf("%d",i);

}

(O(1

כי זה מספק קבוע.

גם אם הלולאה הייתה רצה עד מיליארד זה הייתה אותה תשובה.

זה לא משנה אם זה מספר קבוע של פעמים אותה פקודה מתבצעת כמה פעמים אז זה

סיבוכיות N

אל תבלבל אותו סתם

אם זה רץ מיליון וחצי פעם זה עדיין O(1)

זה O)N( רק אם יש איזשהי תלות בN

כמו לדגומא

for (i=1; i<n;i++)

HELLO WORLD

זה O)N(

אז אתה רוצה להגיד שאם יש לי כמה לולאות מכוננות

זה עדיין 1 ולא N בחזקת משהו ?

זה נשמע לי מוזר ועד כמה שאני זוכר שלמדתי את זה זה לא כחה

אם תעשה אותו מספר פעולות לכל קלט אז זה o(1)

אם זה תלוי ליניארית בקלט זה o(n)

זה לא אושן, זה O של!.

הסיבוכיות של הפונקציה זה O של 1.

O של N זה כאשר יש לך לולאה שמתבצעת N פעמים כאשר N הוא לא פרמטר ולא קבוע, אלא משתנה.

O של N בריבוע זה כאשר יש לולאה בתוך לולאה.

O של logn זה כאשר יש לך למשל משהו כמו חיפוש בינארי.

קוראים את זה "או של n", או אם רוצים לדייק "או גדול" או "או קטן" (ויש גם אומגה שכבר הספקתי לשכוח מה הוא אומר)

ההגדרה המתמטית של O(f(n)) היא משהו כמו -

נניח ש- g(n) מתארת את מספר הפעולות המדוייק שלך כתלות ב- n (אורך הקלט)

האלגוריתם שלך הוא O(n) אם במקרה הכי גרוע

g(n)/f(n) 

מתכנס לקבוע.

שזה בדר"כ אומר - תבנה פונקציה שמתארת את מספר הפעולות, תשאיר רק את האלמנט ששואף הכי מהר לאינסוף, ותזרוק את המקדם שלו.

אומגה זה חסם תחתון

O זה חסם עליון

תטה זה חסם הדוק

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

כמו שנאמר, יש O, אומגה וטתה.

מה שמעניין זה לרוב ה O, שמציין את המקרה הגרוע ביותר. אומגה זה הכי לא מעניין, כי זה המקרה הטוב ביותר, שב99% מהמקרים זה 1.... טתה זה המקרה הממוצע, וזה כבר מתמטיקה כבדה מידיי...

הסדר של סדרי הגודל מהטוב לרע הוא:

O(1)
 O(logN)
O(N)
O(N*logN)
O(N^2)
O(N^3)
O(N^...)
O(2^N)
O(3^N)

ה4 הראשונים הם הכי טובים, והכי נפוצים...

N^2

והלאה זה כבר פחות טוב, ובמקרה כזה נוהגים לחזור ולשפר את האלגוריתם....

2^N

זה ממש ממש ממש גרוע, וצריך לשנות את האלגוריתם...

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

קודם כל צריך למצוא את פונקציית זמן הריצה. בפונקציות איטרטיביות זה לא בעייה..... הנוסחה הכללית היא C*N + D כאשר C זה הפעולות שחוזרות על עצמן, D זה פעולות חד פעמיות, וN זה הפולינום (לפי הלולאות, וכו' וכו'...). למצוא את O כאן זה לא בעייה.. סדר הגודל של הפולינום הגדול ביותר בפונקציה זה ה O (יכולים להיות כמה C*N, כאשר יש כמה לולאות שלא קשורות אחת לשנייה בפונקצייה אחת..)

ברקורסיה זה קצת יותר מורכב. פונקציית זמן הריצה נראית ככה:

T(n)=2*T(n/2) + f(n)

כאשר T(n/2) זה הקריאה הרקורסיבית, הn/2 זה השינוי שאתה שולח לפונקצייה (במקרה הזה מדובר בשיטת הפרד ומשול, שבה מחלקים את הקבוצה שעובדים עליה ל2 חלקים או יותר, ועובדים על כל חלק... מאד יעיל ביחס לn-1), ה 2* זה מספר הפעמים שאתה קורא לרקורסיה (זה רק דוגמה... זה יכול להיות כל דבר...), וf(n) זה הפעולות הנוספות בפונקציה חוץ מהקריאות הרקורסיביות.

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

בהצלחה

כדי להשוות בין שני סדרי גודל, קל להשתמש בכלל לופיטל, כי יש עוד הרבה באמצע (אני זוכר אפילו תרגיל מעצבן כזה שנתנו לנו)

במדעי המחשב דווקא הרבה פעמים מעניין המקרה הממוצע, כאשר מניחים התפלגות מסוימת על הקלט.

ככה למשל מראים שאפשר לעשות מערך דינאמי שהכנסת איבר היא ( o(1 למרות שמדי פעם מגדילים אותו. (השתמשתי ב"או קטן" בכוונה).

בכלל לא סיבכתם התפלגות, מקרה ממוצע, לופיטל

תחשוב על זה שאתה רוצה לדעת מה התלות של זמן הריצה בקלט.

אם אין תלות זה או של 1.

אם יש תלות ליניארית כלומר ללולאה שעוברת על כל הקלט זה או של N

אם זמן הריצה הוא לעבור על הקלט בלולאה מקוננת אז זה או של N^2.

וכו'...