תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות) אין תקציר עריכה |
Johnny Zoo (שיחה | תרומות) מאין תקציר עריכה |
||
שורה 3:
בפרק זה נלמד על נושאים שמתקרבים גם לענפים התיאורטיים יותר של מדעי המחשב, והם בעלי השלכות חשובות לתוכניות שתכתבו. נכיר כמה מושגים מעולם מדעי המחשב, ונראה כמה דרכים מתקדמות יותר לאחסון של מידע.
==יעילות==
נעסוק כאן בקצרה בחלק התיאורטי. הוא לא הכרחי לשימוש מעשי במבני הנתונים שנראה בחלק השני, אך מומלץ מאוד ללמוד אותו כדי להבין טוב יותר את מבני הנתונים השונים שנראה.
שורה 55:
אופן החישוב של סיבוכיות אלגוריתם מסויים מבוסס על קצב הגידול במספר הפעולות של אלגוריתם מסויים ככל שהקלט גדל. לכן, בחישוב הסיבוכיות אפשר להתעלם מגדלים קבועים. לגבי פעולות בסיסיות כמו פעולות אריתמטיות פשוטות, השוואות בין משתנים וכדומה, נוכל להניח שהן דורשות פעולה בודדת - <math dir="ltr">\displaystyle O(1)</math>. זה לא מדוייק (למשל: למרות שנתייחס כך למרבית החישובים המתמטיים, יש מהם שדורשים מספר פעולות רב שתלוי באורך הקלט הניתן להם), אך מספיק לצרכינו.
כעת חישוב הסיבוכיות (של המקרה הגרוע) מתבסס על מספר הפעולות הבסיסיות הדרושות לנו עד שהאלגוריתם מגיע לסיומו, בדומה לאופן בו חישבנו את הסיבוכיות בשתי הדוגמאות שלעיל.
ההצדקה לאופן הגס של חישוב הסיבוכיות נובעת מכך שמטרת הסיבוכיות היא לאמוד '''סדרי גודל''': באיזו מהירות צומח מספר הפעולות הדרוש כאשר הקלט הולך וגדל. מספר הפעולות שידרוש אלגוריתם שהסיבוכיות שלו היא <math dir="ltr">\displaystyle O(n)</math> יגדל בצורה פרופורציונלית לגידול בקלט. מספר הפעולות שידרוש אלגוריתם שהסיבוכיות שלו היא <math dir="ltr">\displaystyle O(n^2)</math> יגדל באופן מהיר יותר (אך עדיין סביר, בדרך כלל), בעוד מספר הפעולות עבור אלגוריתם <math dir="ltr">\displaystyle O(Log(n))</math> יגדל במהירות קטנה יותר. אלגוריתם שסיבוכיותו היא <math dir="ltr">\displaystyle O(2^n)</math> יהיה כרוך בגידול עצום במספר הפעולות, ועבור קלטים גדולים מאוד הוא יהיה כמעט חסר תועלת.
מומלץ לעבור על ההגדרות מתמטיות המדויקות יותר, אותן ניתן לראות ב[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים|ספר על מבני נתונים ואלגוריתמים]], בחלק העוסק באלגוריתמים. ▼
▲נגענו כאן רק בקצה המזלג בנושא רחב. להבנה טובה יותר, מומלץ לעבור על ההגדרות מתמטיות המדויקות יותר, אותן ניתן לראות ב[[מבני נתונים ואלגוריתמים - מחברת קורס/אלגוריתמים|ספר על מבני נתונים ואלגוריתמים]], בחלק העוסק באלגוריתמים.
==מבני נתונים==
| |||