תכנות מתקדם ב-Java/מבני נתונים מתקדמים: הבדלים בין גרסאות בדף
תוכן שנמחק תוכן שנוסף
Johnny Zoo (שיחה | תרומות) מאין תקציר עריכה |
Johnny Zoo (שיחה | תרומות) אין תקציר עריכה |
||
שורה 3:
בפרק זה נלמד על נושאים שמתקרבים גם לענפים התיאורטיים יותר של מדעי המחשב, והם בעלי השלכות חשובות לתוכניות שתכתבו. נכיר כמה מושגים מעולם מדעי המחשב, ונראה כמה דרכים מתקדמות יותר לאחסון של מידע.
==סיבוכיות==
נעסוק כאן בקצרה בחלק התיאורטי. הוא לא הכרחי לשימוש מעשי במבני הנתונים שנראה בחלק השני, אך מומלץ מאוד ללמוד אותו כדי להבין טוב יותר את מבני הנתונים השונים שנראה.
===אלגוריתמים===
[[w:he:אלגוריתם|אלגוריתם]] - דרך
אלגוריתם לדוגמה: מציאת האיבר המקסימלי במערך לא ממויין שמכיל מספרים שלמים וחיוביים. למען הפשטות, נקבע שהאלגוריתם יחזיר 0 במידה והמערך ריק.
# אתחל משתנה בשם Max וקבע אותו ל-0.
# עבור על איברי המערך בזה אחר זה. אם נתקלת באיבר שגדול מ-Max - קבע את Max להיות איבר זה.
שורה 15:
קל לראות שאם נשתמש באלגוריתם נוכל למצוא את המספר המקסימלי במערך נתון. אפשר גם לראות שאפשר להפוך בקלות יחסית את האלגוריתם הזה לשיטה בג'אווה שמקבלת מערך כזה ומחזירה את הדרוש.
למשל:
<source lang="java">
public static int findMaxInt(int[] arr) {
if(arr == null) return 0;
int max = 0;
for(int i=0; i<arr.length; i++) {
if(arr[i] > max) max = arr[i];
}
return max;
}
</source>
מכיוון שאלגוריתמים הם מסודרים ומוגדרים היטב, קל לתרגם אלגוריתמים לתוכניות מחשב. מתכנתים רבים, בבואם לכתוב תוכנית, יעדיפו לתכנן אותה תחילה "על הנייר", ולתכנן את האלגוריתמים הדרושים (כמו גם את עיצוב התוכנית, הממשק, ושאר הפרטים החשובים), לפני הכתיבה בפועל של התוכנית.▼
{{אתגר|כיצד תשנו את האלגוריתם כך שיעבוד גם בלי ההנחה שכל המספרים במערך הם חיוביים? חשבו על המקרה בו כל המספרים הם שליליים.}}
▲באופן כללי, מכיוון שאלגוריתמים הם מסודרים ומוגדרים היטב, קל לתרגם אלגוריתמים לתוכניות מחשב. מתכנתים רבים, בבואם לכתוב תוכנית, יעדיפו לתכנן אותה תחילה "על הנייר", ולתכנן את האלגוריתמים הדרושים (כמו גם את עיצוב התוכנית, הממשק, ושאר הפרטים החשובים), לפני הכתיבה בפועל של התוכנית.
===סיבוכיות===
[[w:he:סיבוכיות|סיבוכיות]] היא דרך לאמוד את יעילותו של אלגוריתם
====סימונים====
נהוג לסמן את גודל הקלט באות <math dir="ltr">\displaystyle n</math>. את פונקציית הסיבוכיות של המקרה הגרוע ביותר מסמנים באות <math dir="ltr">\displaystyle O</math>.
אם נרצה לומר, לדוגמה, כי סיבוכיות של אלגוריתם מסויים היא <math dir="ltr">\displaystyle n^2</math> נסמן זאת ב-<math dir = "ltr">\displaystyle O(n^2)</math>
====חישוב הסיבוכיות====
==מבני נתונים==
עד כה נתקלנו בכמה מבני נתונים: מערך, וקטור, ורשימה מקושרת, כל אחד מהם עם יתרונותיו וחסרונותיו. עתה נראה כמה מבנים חדשים. הכלל נשאר זהה: לא קיים מבנה נתונים שעדיף באופן מוחלט על האחרים, אך במרבית המקרים ניתן לכתוב תוכנית יעילה יותר בעזרת בחירה נכונה של מבני הנתונים בהם נשתמש.
===עץ בינארי===
===טבלת גיבוב===
| |||