חיפוש בינארי
חיפוש בינארי (גם "אריה במדבר") מוצא מקום של מספר במערך סדור. סדור פירושו שהמספרים מסודרים מהקטן לגדול. המטרה היא לדעת היכן נמצא מספר בתוך רשימה ממוּיינת. השיטה חוסכת הרבה בדיקות. בודקים את האיבר באמצע הרשימה. אם זה המספר, מסיימים. אם המספר קטן יותר, מחפשים בחצי השמאלי. אם גדול יותר, מחפשים בח...
אלגוריתם חיפוש
אלגוריתם חיפוש הוא דרך למצוא פריט במחשב. מבנה נתונים הוא איך מסדרים את הפריטים. חיפוש ממצה אומר לבדוק אם הפריט נמצא, ולשלוף אותו אם כן. יש חיפוש בכוח גס: בודקים פריט פריט עד שמוצאים. זה עובד אבל איטי כשיש הרבה פריטים. אם הפריטים מסודרים לפי סדר אפשר להשתמש בחיפוש בינארי. בחיפוש בינארי בודקים את האמ...
סיבוכיות
סיבוכיות היא מדד למספר המשאבים שמחשב צריך כדי לפתור בעיה. המשאבים העיקריים הם זמן (כמה זמן לוקח) וזיכרון (כמה מקום בתוכו). לפעמים בודקים גם כמה מחשבים קטנים עובדים ביחד. "בעיה" היא קבוצה של שאלות דומות. שאלה בודדת נקראת מופע. לדוגמה, בעיית הפירוק: למצוא את הגורמים של מספר. השאלה "למה 15 מתפרק?" היא...
עץ AVL
עץ AVL הוא סוג של עץ במחשבים. זהו "עץ חיפוש בינארי". זה אומר שלכל צומת יש עד שני בנים. בצד שמאל ערכים קטנים יותר. בצד ימין ערכים גדולים יותר. עץ AVL שומר על איזון. לכל צומת יש מספר שנקרא "גורם האיזון". זהו ההפרש בין הגובה של הצד השמאלי לזה של הצד הימני. הגורם יכול להיות 1, 0 או -1 בלבד. כך העץ נשא...
אלגוריתם מיון
מיון הוא דרך לסדר דברים לפי מפתח. למשל: לסדר אנשים לפי שם משפחה. יש שני סוגים: מיון עולה, שבו הקטן ביותר ראשון, ומיון יורד, שבו הגדול ראשון. מיון עוזר לעבוד עם מסדי נתונים. מסד נתונים שומר רשימות מסודרות שנקראות אינדקס. אינדקס הוא רשימה שמקלה על מציאת פריטים. כשנתונים מסודרים, אפשר למצוא דברים מה...
איטרציה
איטרציה היא פעולה שחוזרת שוב ושוב. כל חזרה נקראת איטרציה. כשעושים הרבה חזרות זה תהליך חזרורי. במחשב יש לולאות. לולאה היא קטע קוד שחוזר על עצמו עד שמסיימים. לכל איטרציה יש גודל. הכוונה כמה פקודות יש או כמה זמן היא לוקחת. מספר האיטרציות יכול להיות אפס או הרבה. ברשימה של 1,024 פריטים סריקה רגילה ...
עץ אדום שחור
עץ אדום-שחור הוא עץ שמאורגן כדי לחפש דברים מהר. כל נקודה (צומת) בצבע אדום או שחור. צבעים אלה עוזרים לשמור את העץ מאוזן. עץ חיפוש בינארי מסודר כך שמציאת פריט קלה. אם העץ לא מאוזן, החיפוש איטי. בצבעים של עץ אדום-שחור מונעים מצבים כאלה. עלים הם הפניות ריקות, כלומר "כלום". בדרך כלל לא שומרים עליהם בזי...
גישה ישירה
גישה ישירה היא דרך להיכנס למידע בלי לעבור על כל השאר. תקליט מאפשר להגיע לכל נקודה על פניו על ידי הזזת המחט. בקלטת וידאו הגישה סדרתית. סדרתית אומרת שצריך להריץ קדימה או אחורה כדי להגיע למקום. יש גם ההשוואה של מגילה לעומת ספר. במחשבים יש מבנים כמו מערך (קבוצה מסודרת של פריטים). מערך מאפשר גישה ישירה. ...
אלגוריתם הפרד ומשול
הפרד ומשול היא דרך לפתור בעיות על ידי חלוקה לחלקים קטנים יותר. כל חלק הוא בעיה דומה. אחרי שמפתרים את כל החלקים, מחברים את התשובות ביחד. אומרים שהדרך היא רקורסיה. רקורסיה זו קריאה של פונקציה לעצמה. אפשר גם לעשות את זה בלי רקורסיה, בעזרת מחסנית (מבנה שמאחסן דברים לפי סדר). השיטה טובה לבעיות קשות. אם...