מערך (Array)

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

 

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

One-dimensional Array
  • נהוג לצייר את המערך כשורה של תאים.
  • אנו מתחילים לספור את האינדקסים כמו כל דבר במדעי המחשב ב 0 (ולא ב 1).
  • שם המערך הוא A.
  • כדי לפנות לתא במערך, אנו נרשום: [A[6. בכך נפנה לתא בעל האינדקס 6 (תא מספר 6) שבו נמצא הערך 101 (שימו לב כי זה האיבר השביעי במערך).
  • מבנה זה של מערך נקרא מערך חד מימדי, שכן הינו בעל מימד אחד, שורה אחת.

 

מערך דו מימדי

מערך דו מימדי הינו מערך בעל כמה שורות (בניגוד למערך חד מימדי בו ישנה שורה אחת בלבד) ושקול למטריצה במתמטיקה. מערך דו מימדי של מספרים שלמים יראה כך:

 012345
045239282340
1347683106092
2723793941865
315983269527
49234596489

כשנרצה לפנות לתא במערך, אנו נרשום [A[0,4 ובכך ניגש לשורה מס’ 0 ולעמודה מס’ 4, ובתא הזה מופיע הערך 34 (יש לציין כי לא בכל השפות ניגשים קודם למספר השורה ולאחר מכן לעמודה).

 

תכונות המערך

כמו שניתן לראות, מערך הינו אוסף של משתנים מסוג מסויים, במערך ניתן לשים מגוון סוגי משתנים, אך ברגע שהגדרנו את המערך להכיל סוג של משתנה כל המערך מכיל את אותו הסוג. ז”א שאם נגדיר את המערך A להכיל משתנה מסוג int (קיצור של integer - מספרים שלמים), כל התאים במערך יקבלו אך ורק int, ולא יתכן כי נכניס בתא אחד int (מספר שלם), ובשני צירוף של תווים (string - מחרוזת תווים או במילים פשוטות: מילים).

גישה לתא במערך, תתבצע בזמן ריצה (O(1 מכיוון שאנו יודעים בדיוק לאיזה תא אנו רוצים לגשת, הפעולה תדרוש מאיתנו זמן ריצה קבוע ובסיסי: 1. בנוסף, המערך דורש בדיוק את כמות הזיכרון הנדרשת עבור הנתונים עצמם, ז”א שבמידה וישנם 9 נתונים הוא ידרוש בדיוק 9 תאים ולא יותר (להבדיל ממבני נתונים אחרים אותם נפגוש בהמשך).

אחד החסרונות הגדולים במערך הוא פעולת מחיקת איברים, במידה ונרצה למחוק איבר מהמערך אנו נצטרך להעביר את שאר הערכים בתאים שאחריו, כל אחד, אחד אחורה. לדוגמה: אם נרצה למחוק את הערך בתא [A[6 אז לאחר המחיקה, נצטרך להעביר את הערך בתא [A[7 לתא [A[6, ולאחר מכן את הערך בתא [A[8 לתא [A[7. מכיוון שאנו לא יודעים איזה ערך נרצה למחוק כל פעם, ניקח את המקרה הגרוע ביותר, שהינו גודל המערך (למקרה ונרצה למחוק את הערך בתא הראשון - [A[0), נסמן את גודל המערך ב n ולכן זמן הריצה של פעולת המחיקה יהיה (O(n.

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

 

שימושי המערך

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

שימו לב, למערך חד מימדי נהוג לקרוא פשוט “מערך”, בעוד כשנרצה לציין מערך דו מימדי, נציין במפורש “מערך דו מימדי”.

 

סימונים אסימפטוטים

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

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

אך לקלטים שונים יכולים להיות זמני ריצה שונים, לדוגמה אם נקבל כקלט מערך שכבר ממוין, יש אלגוריתם שיעבור על n התאים שבו, יראה כי כל התאים כבר נמצאים במקומם הנכון, וזהו. לעומת זאת אם נכניס כקלט מערך ממוין הפוך (ז”א מהגדול לקטן), אלגוריתם זה יעבור על n התאים n פעמים (n*n או n^2).

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

  • (2^O(n ה O (או גדולה) מקביל ל’מקסימום’, ז”א שזמן הריצה יהיה מקסימום (במקרה הגרוע ביותר) n^2.
  • (Θ(n^2 (עיגול וקו בתוכו, באנגלית: Theta) מקביל ל’בדיוק’, ז”א שלכל קלט זמן הריצה יהיה בדיוק n^2.
  • (Ω(n^2 (באנגלית: Omega) מקביל ל’מינימום’, ז”א זמן הריצה יהיה מינימום n^2.

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

 

לסיכום

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