השאלות והתשובות מראיונות עבודה: אלגוריתמים בג'אווה, חלק 1

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

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

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

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++) { // An ordinary outer loop
           int min = i;

           for (int j = i + 1; j < array.length; j++) { // An ordinary loop, but one that accounts for the sorted numbers
               if (array[j] < array[min]) {
                   min = j;
               }
           }
           int temp = array[i];     // Put the sorted number in the proper cell
           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 is the dividing marker
           int temp = array[i]; // Make a temporary copy of the marked element
           int j = i;
           while (j 	> 0 && array[j - 1] >= temp) { // Until a smaller element is found
               array[j] = array[j - 1]; // We shift the element to the right
               --j;
           }
           array[j] = temp;   // Insert the marked element in its proper place
       }
   }
}

סוג זה של מיון עדיף על אלו שתוארו לעיל, מכיוון שלמרות העובדה שיש לו אותו זמן ריצה 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} במערך הכללי, יש לנו : {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 = 1; numberOfGroup < length - step; numberOfGroup++) { // We pass over all of our groups
              int j = numberOfGroup;
               while (j >= 0 && array[j] > array[j + step]) { // Insertion sort inside the group
                   int temp = array[j];
                   array[j] = array[j + step];
                   array[j + step] = temp;
                   j--;
               }
           }
           step = step / 2; // Shrink the interval
       }
   }
}

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

מיון מהיר

זהו אחד האלגוריתמים הפופולריים ביותר, ולכן כדאי לשים לב אליו במיוחד. עיקרו של אלגוריתם זה הוא שרכיב ציר נבחר ברשימת אלמנטים. אנחנו ממיינים את כל שאר האלמנטים ביחס לאלמנט הציר. ערכים הנמוכים מאלמנט הציר נמצאים בצד שמאל. ערכים גדולים יותר ממה שהם מימין. לאחר מכן, נבחרים רכיבי pivot גם בחלק הימני והשמאלי, ואותו דבר קורה: הערכים ממוינים ביחס לאלמנטים הללו. לאחר מכן נבחרים רכיבי pivot בחלקים החדשים שנוצרו, וכן הלאה עד שנקבל רצף ממוין. היישום הבא של 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 for exiting recursion if the array length is 0
           return;

       if (min> = max) // Terminate the recursion, since there is nothing to divide
           return;


       int middle = min + (max - min) / 2; // Select the middle
       int middleElement = array[middle];


       int i = min, j = max;
       while (i <= j) { // Every element less than the middle element will be to the left, and large ones will be to the right
           while (array[i] < middleElement) {
               i++;
           }
           while (array[j] > middleElement) {
               j--;
           }

           if (i <= j) { // Swap places
               int temp = array[i];
               array[i] = array[j];
               array[j] = temp;
               i++;
               j--;
           }
       }

       if (min < j) // Make a recursive call on the elements that are less than middle
           recursionFastSort(array, min, j);

       if (max > i) // Make a recursive call on the elements larger than middle
           recursionFastSort(array, i, max);
   }
}

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

מיזוג מיון

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

לחלק:

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

לִכבּוֹשׁ:

כאן מתחילים את התהליך שנתן לאלגוריתם את שמו: מיזוג. לשם כך, אנו לוקחים את שני המערכים הממוינים שנוצרו וממזגים אותם לאחד. במקרה זה, הקטן ביותר מבין הרכיבים הראשונים של שני המערכים נכתב במערך המתקבל. פעולה זו חוזרת על עצמה עד שכל האלמנטים בשני המערכים הללו הועתקו. כלומר, אם יש לנו שני מערכים מינימליים {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); // Array for sorting
       int[] bufferArr = new int[array1.length];// Buffer array
       return recursionMergeSort(sortArr, bufferArr, 0, array1.length);
   }


   public static int[] recursionMergeSort(int[] sortArr, int[] bufferArr,
                                          int startIndex, int endIndex) {
       if (startIndex> = endIndex - 1) { // Return the array when there is only one element left in the array range under consideration
           return sortArr;
       }

       // Make a recursive call to get two sorted arrays:
       int middle = startIndex + (endIndex - startIndex) / 2;
       int[] firstSortArr = recursionMergeSort(sortArr, bufferArr, startIndex, middle);
       int[] secondSortArr = recursionMergeSort(sortArr, bufferArr, middle, endIndex);

       // Merge the sorted arrays:
       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;
   }
}

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

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

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

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

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

public class Item implements Comparable {
   private String name;
   private int weight;
   private int value;

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

   public String getName() {
       return name;
   }

   public int getWeight() {
       return weight;
   }

   public int getValue() {
       return value;
   }

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

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

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

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

   public int getMaxWeight() {
       return maxWeight;
   }

   public int getCurrentValue() {
       return currentValue;
   }

   public int getCurrentWeight() {
       return currentWeight;
   }

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

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

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

public class Solution {

   public static void main(String[] args) {
       List<Item> items = new ArrayList<>();
       items.add(new Item("Guitar", 7, 800));
       items.add(new Item("Iron", 6, 500));
       items.add(new Item("Tea pot", 3, 300));
       items.add(new Item("Lamp", 4, 500));
       items.add(new Item("Television", 15, 2000));
       items.add(new Item("Vase", 2, 450));
       items.add(new Item("Mixer", 2, 400));
       items.add(new Item("Blender", 3, 200));

       Collections.sort(items);

       Bag firstBag = new Bag(30);

       fillBackpack(firstBag, items);

       System.out.println("Knapsack weight is " + firstBag.getCurrentWeight() +
               ". The total value of items in the knapsack is " + firstBag.getCurrentValue());
}
}

ראשית, אנו יוצרים רשימה של פריטים וממיינים אותה. אנו יוצרים אובייקט תיק עם קיבולת של 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 items) {
   Map<Double, Item> sortByRatio = new TreeMap(Collections.reverseOrder());
   for (Item item : items) {
       sortByRatio.put((double)item.getValue() / 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("The weight of the knapsack is " + secondBag.getCurrentWeight() +
       ". The total cost of items in the knapsack is " + secondBag.getCurrentValue());

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