עזרה בהבנת סיבוכיות זמן וסיבוכיות מקום

[אסתר א]

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

 

[(; Cool-It]

גמאני אשמח לחומר איכותי בנושא.
יש לי רצון לדעת ולהבין את הנושא לעומק. (אולי משקעים מהיעדר תואר?... )

 

[undo]

אם יש לי אפשרות לעזור - אשמח לנסות.
איזו צורה של עזרה צריך?

 

[אסתר א]

אם יש לי אפשרות לעזור - אשמח לנסות.
איזו צורה של עזרה צריך?

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

אבל כל הנושא של logN
logNlog
או כשמחברים כמה סימונים ביחד ויוצא משהו מוזר
למשל
O(logN) + O(N^2) =

בעצם אני צריכה הסברים ממישהו שמבין את הנושא כמו שצריך

 

[undo]

אולי תציגי דוגמה?
יהיה יותר ברור מה את מחפשת.

 

[שירה 123]

יש הסברים מצויינים בקרוסרה- תכתבי שם אלגורתמים .
אני אישית למדתי את הנושא משם.

 

[i am]

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

אבל כל הנושא של logN
logNlog
או כשמחברים כמה סימונים ביחד ויוצא משהו מוזר
למשל
O(logN) + O(N^2) =

בעצם אני צריכה הסברים ממישהו שמבין את הנושא כמו שצריך

פני באישי i.am.in.prog בג'ימייל

 

[s976]

יש הרצאות של שי תבור (מרצה בפתוחה)
יש לו על זה שיעור אחד או שניים (כל אחד של שלוש שעות נדמה לי)
לא נראה לי שתמצאי משהו טוב וברור יותר.
יש את זה בדרופבוקס https://www.dropbox.com/sh/vkn04uf60ein8lw/AADAytcM0jstq6gl845UZXGma?dl=0&lst=
ויש גם באתר שלו כנראה http://shaytavor.com/

 

[nhfk]

אם לא הסתדרת תכתבי לי
myklyrp41אין לכתוב כתובת מייל

 

[אסתר א]

יש הרצאות של שי תבור (מרצה בפתוחה)
יש לו על זה שיעור אחד או שניים (כל אחד של שלוש שעות נדמה לי)
לא נראה לי שתמצאי משהו טוב וברור יותר.
יש את זה בדרופבוקס https://www.dropbox.com/sh/vkn04uf60ein8lw/AADAytcM0jstq6gl845UZXGma?dl=0&lst=
ויש גם באתר שלו כנראה http://shaytavor.com/

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

 

[שתים]

בגדול אם פעולה/לולאה/פונקציה תלויה במשתנה אז מכניסים את ה N וסתם פעולות פשוטות לא נספרות.
לדוגמא: for שעובר על משתנה i ואז עושה 2 פעולות נוספות.
מה ששוקל פה זה בעצם מספר הפעמים שהוא יבצע את הפעולה ואילו 2 הפעולות הנוספות הן זניחות.
לכן נקרא לזה O +2 אבל ה2 הוא זניח.
ולכן for שבתוכו יש for יחשב כ O n בריבוע.
לעומת זאת יש פעולות שאמנם תלויות ב n אבל תכלס הן חכמות ומבצעות מספר פעולות נמוך יחסית.
לדוגמא אלגוריתם quick sort עובר על מערך בגודל n אבל מסדר אותו תוך מספר פעולות יחסי שנמוך מהרגיל . O (nlogn)
לעומת bubble sort שעבור מערך בגודל n הוא באמת עובר על כל תא ותא ומשווה אותו לעומת כל תא ותא האחרים.
בעצם הוא עושה for כפול ולכן סיבוכיות זמן הריצה שלו הוא O(n2).

 

[נסיון9876]

לדוגמא אלגוריתם quick sort עובר על מערך בגודל n אבל מסדר אותו תוך מספר פעולות יחסי שנמוך מהרגיל . O (nlogn)

במקרה הממוצע.
במקרה הגרוע גם כן בשניה.

וגם לולאה כפולה היא לא תמיד N בשניה