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