מה הם שואלים בראיון: סקירת אלגוריתמים, חלק 1

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

1. סקירה כללית של אלגוריתמי מיון מערכים:
   • מיון בועות,
   • מיון בחירה,
   • מיון הכנסה,
   • מיון מעטפת,
   • מיון מהיר,
   • מיזוג מיון.
2. אלגוריתם חמדן.
3. אלגוריתמים למציאת נתיבים:
   • זוחל לעומק
   • זחילה רחבה.
4. אלגוריתם התחבורה הוא האלגוריתם של דיקסטרה.

ובכן, בלי להכביר מילים, בואו ניגש לעניינים.

1. סקירה כללית של אלגוריתמי מיון

מיון בועות

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

• השוו שני מספרים;
• אם המספר בצד שמאל גדול יותר, החלף אותם;
• להזיז עמדה אחת ימינה.

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

public class Solution {
   public static void main(String[] args) {
    int[] testArr = new int[]{6,3,8,2,6,9,4,11,1};
    bubbleSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void  bubbleSort(int[] array) {
       for(int i = array.length -1; i > 1; i--) {
         for (int j = 0; j < i; j++) { //
             if (array[j] > array[j+1]) {
                 int temp = array[j];
                 array[j] = array[j+1];
                 array[j+1] = temp;
             }
         }
       }
   }
}

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

מיון לפי בחירה

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

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 2, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {

       for (int i = 0; i < array.length-1; i++) { // внешний обычный  цикл
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // обычный цикл, но с отчетом с сортированных чисел
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // вставка отссортиованного числа, в положеную ему ячейку
           array[i] = array[min];
           array[min] = temp;
       }
   }
}

אלגוריתם זה עדיף על מיון בועות, מכיוון שכאן מספר התמורות הדרושות מצטמצם מ-O(N²) ל-O(N): איננו דוחפים אלמנט אחד דרך כל הרשימה, אך עם זאת, מספר ההשוואות נשאר O(N² ) . למי שרוצה ללמוד עוד על אלגוריתם זה, אני ממליץ על חומר זה .

מיון הכנסה

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

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       insertionSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void insertionSort(int[] array) {

       for (int i = 1; i < array.length; i++) { // i - разделяющий маркер
           int temp = array[i]; // делаем копию помеченного element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // пока не будет найден меньший элемент
               array[j] = array[j - 1]; // сдвигаем элементы вправо
               --j;
           }
           array[j] = temp;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

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

מיון מעטפת

מיון זה, מטבעו, הוא מיון הכנסה שונה. על מה אני מדבר? בוא נלך לפי הסדר. שלב נבחר, וישנן גישות רבות לבחירה זו. לא ניכנס לנושא הזה בפירוט רב מדי. בואו נחלק את המערך שלנו לשניים ונקבל מספר מסוים – זה יהיה הצעד שלנו. לכן, אם יש לנו 9 אלמנטים במערך, אז הצעד שלנו יהיה 9/2 = 4.5 . אנו פוסלים את החלק השברי ומקבלים 4 , שכן מדדי מערך הם רק מספרים שלמים. בעזרת שלב זה ניצור קשרים לקבוצות שלנו. אם לאלמנט יש אינדקס 0, אז האינדקס של האלמנט הבא בקבוצה שלו הוא 0+4 , כלומר 4 . לאלמנט השלישי יהיה אינדקס של 4+4 , לרביעי יהיה אינדקס של 8+4 וכן הלאה. עבור הקבוצה השנייה, האלמנט הראשון יהיה 1,5,9…. בקבוצה השלישית והרביעית הדברים יהיו בדיוק אותו הדבר. כתוצאה מכך, ממערך המספרים {6,3,8,8,6,9,4,11,1} נקבל ארבע קבוצות: I - {6,6,1} II - {3,9} III - {8,4} IV - {8,11} הם שומרים על מקומותיהם במערך הכללי, אך עבורנו הם מסומנים כחברים באותה קבוצה: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } בהמשך הקבוצות הללו מתרחש מיון ההוספה , ולאחר מכן הקבוצות ייראו כך: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} במערך הכללי, התאים שתפוסים על ידי הקבוצות , יישארו זהים, אך הסדר בתוכם ישתנה, לפי סדר הקבוצות שלמעלה: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } המערך קצת יותר מסודר, לא? השלב הבא יחולק ב-2: 4/2 = 2 יש לנו שתי קבוצות: I - {1,4,6,8,6} II - {3,8,9,11} מערך כללי B: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } אנו עוברים על שתי הקבוצות באמצעות אלגוריתם מיון ההכנסה ומקבלים מערך: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} כעת המערך שלנו כמעט ממוין. האיטרציה האחרונה של האלגוריתם נשארת: נחלק את הצעד ב-2: 2/2 = 1. נקבל קבוצה, כל המערך: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } לפי שאנו עוברים על אלגוריתם מיון ההוספה ומקבלים: { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } בואו נראה כיצד נוכל להציג את המיון הזה בקוד Java:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       sortBySelect(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void sortBySelect(int[] array) {
       int length = array.length;
       int step = length / 2;
       while (step > 0) {
           for (int numberOfGroup = 0; numberOfGroup < length - step; numberOfGroup++) {// проходим по всем нашим группам
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) {//sorting вставкой внутри группы
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // уменьшаем наш шаг
       }
   }
}

נכון לעכשיו, האפקטיביות של מיון מעטפת לא ממש מבוססת, שכן התוצאות שונות במצבים שונים. הערכות שהתקבלו מניסויים נעות בין O(N ^3/2 ) ל- O(N ^7/6 ) .

מיון מהיר

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

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       fastSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static void fastSort(int[] array) {
       recursionFastSort(array, 0, array.length - 1);
   }


   public static void recursionFastSort(int[] array, int min, int max) {
       if (array.length == 0)// condition выхода из рекурсии,  если длина массива равна 0
           return;

       if (min >= max) //выходим, так How нечего уже делить
           return;


       int middle = min + (max - min) / 2;  // выбираем середину
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) {  // относительно element middle определяемменьшие элементы слева, большие справа
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) {      //меняем местами
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // запускаем рекурсию с elementми меньшими чем middle
           recursionFastSort(array, min, j);

       if (max > i)// запускаем рекурсию с elementми большими чем middle
           recursionFastSort(array, i, max);
   }
}

ללא ספק, אלגוריתם ה-quicksort נחשב לפופולרי ביותר, שכן ברוב המצבים הוא פועל מהר יותר מאחרים, בזמן O(N*logN) .

מיזוג מיון

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

לַחֲלוֹק:

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

לִכבּוֹשׁ:

כאן מתחיל התהליך שנותן את השם למיזוג האלגוריתם . לשם כך, קח את שני המערכים המסודרים שנוצרו ומיזג אותם לאחד. במקרה זה, הקטן ביותר מבין האלמנטים הראשונים של שני המערכים נכתב למערך המתקבל, והפעולה הזו חוזרת על עצמה עד שאין יותר אלמנטים בשני המערכים. כלומר, אם יש לנו שני מערכים מינימליים {6} ו- {4} , הערכים שלהם יושוו והתוצאה תיכתב: {4,6} . אם יש מערכים ממוינים {4,6} ו- {2,8} , אז תחילה ישווה את הערך 4 ו -2 , מתוכם 2 ייכתבו למערך המתקבל. לאחר מכן יושוו 4 ו -8 , ירשמו 4 , ובסוף יושוו 6 ו -8 . בהתאם לכך ייכתב 6, ורק אחריו - 8. כתוצאה מכך נקבל את המערך המתקבל: {2,4,6,8} . איך זה יראה בקוד Java? כדי לעבד אלגוריתם זה, יהיה לנו נוח להשתמש ברקורסיה:

public class Solution {
   public static void main(String[] args) {
       int[] testArr = new int[]{6, 3, 8, 8, 6, 9, 4, 11, 1};
       testArr = mergeSort(testArr);
       for (int i : testArr) {
           System.out.println(i);
       }
   }

   public static int[] mergeSort(int[] array1) {
       int[] sortArr = Arrays.copyOf(array1, array1.length);// массив для сортировки
       int[] bufferArr = new int[array1.length];// буферный массив
       return recurtionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recurtionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex >= endIndex - 1) {// выход из массива, когда в рассматриваемом промежутке массива, только один элемент
           return sortArr;
       }

       // запускаем рекурсию, чтобы получить два отсортированных массива:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recurtionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recurtionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Слияние отсортированных массивов:
       int firstIndex = startIndex;
       int secondIndex = middle;
       int destIndex = startIndex;
       int[] result = firstSortArr == sortArr ? bufferArr : sortArr;
       while (firstIndex < middle && secondIndex < endIndex) {
           result[destIndex++] = firstSortArr[firstIndex] < secondSortArr[secondIndex]
                   ? firstSortArr[firstIndex++] : secondSortArr[secondIndex++];
       }
       while (firstIndex < middle) {
           result[destIndex++] = firstSortArr[firstIndex++];
       }
       while (secondIndex < endIndex) {
           result[destIndex++] = secondSortArr[secondIndex++];
       }
       return result;
   }
}

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

2. אלגוריתמים חמדנים

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

1. בחר את הפריט היקר ביותר מבין אלה שטרם נגעו בו.
2. אם זה נכנס לתרמיל שלך, שים אותו שם; אם לא, דלג עליו.
3. עשיתם סדר בכל הפריטים? אם לא, נחזור לנקודה 1, אם כן, אנו בורחים מהחנות, שכן המטרה שלנו כאן הושלמה.

בואו נסתכל על זה, אבל בג'אווה. כך תיראה מחלקת פריט:

public class Item implements Comparable<Item> {
   private String name;
   private int weight;
   private int cost;

   public Item(String name, int weight, int cost) {
       this.name = name;
       this.weight = weight;
       this.cost = cost;
   }

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getCost() {
       return cost;
   }

   @Override
   public int compareTo(Item o) {
       return this.cost > o.cost ? -1 : 1;
   }
}

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

public class Bag {
   private final int maxWeight;
   private List<Item> items;
   private int currentWeight;
   private int currentCost;

   public Bag(int maxWeight) {
       this.maxWeight = maxWeight;
       items = new ArrayList<>();
       currentCost = 0;
   }

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentCost() {
       return currentCost;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

   public void addItem(Item item) {
       items.add(item);
       currentWeight += item.getWeight();
       currentCost += item.getCost();
   }
}

• maxWeight הוא הקיבולת של תרמיל הגב שלנו, שנקבע בעת יצירת האובייקט;
• פריטים - חפצים בתרמיל;
• currentWeight , currentCost - המשקל והעלות הנוכחיים של כל החפצים בתרמיל, אותם אנו מעלים בעת הוספת פריט חדש בשיטת addItem .

בוא נלך למעשה לכיתה, שם כל הפעולות מתרחשות:

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("гитара",7, 800));
       items.add(new Item("утюг",6, 500));
       items.add(new Item("чайник",3, 300));
       items.add(new Item("лампа",4, 500));
       items.add(new Item("телевизор",15, 2000));
       items.add(new Item("ваза",2, 450));
       items.add(new Item("миксер",1, 400));
       items.add(new Item("блендер",3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Вес рюкзака состовляет - " + firstBag.getCurrentWeight() +
               ", общая стоимость вещей в рюкзаке - " + firstBag.getCurrentCost());
}
}

ראשית, אנו יוצרים רשימה של אלמנטים וממיינים אותה. צור אובייקט תיק בקיבולת של 30 יחידות. לאחר מכן, אנו שולחים את האלמנטים ואת אובייקט התיק לשיטת fillBackpack , שבה, למעשה, התרמיל ממולא באמצעות אלגוריתם חמדן:

public static void fillBackpack(Bag bag, List<Item> items) {
   for (Item item : items) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + item.getWeight()) {
            bag.addItem(item);
       }
   }
}

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

public static void effectiveFillBackpack(Bag bag, List<Item> items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getCost() / item.getWeight(), item);
   }

   for (Map.Entry<Double, Item> entry : sortByRatio.entrySet()) {
       if(bag.getMaxWeight() > bag.getCurrentWeight() + entry.getValue().getWeight()) {
           bag.addItem(entry.getValue());
       }
   }
}

כאן אנו מחשבים תחילה את יחס המשקל-מחיר עבור כל פריט. כביכול, כמה עולה יחידה אחת של פריט נתון? ולפי הערכים האלה אנחנו ממיינים את הפריטים שלנו ומוסיפים אותם לתיק שלנו. בוא נרוץ:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

System.out.println("Вес рюкзака составляет - " + secondBag.getCurrentWeight() +
       ", общая стоимость вещей в рюкзаке - " + secondBag.getCurrentCost());

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