Apa yang mereka tanyakan saat wawancara: review algoritma, bagian 1

Selamat sore semuanya! Berbagai jenis algoritme lebih sering digunakan dalam proyek daripada yang Anda kira. Misalnya, kita perlu mengurutkan beberapa data menurut parameter (kolom) tertentu sehingga kita dapat menavigasinya tanpa banyak usaha. Oleh karena itu, tidak ada yang aneh jika selama wawancara kerja mereka mungkin ditanya tentang satu atau beberapa algoritma dasar, dan mungkin diberi tugas untuk mengimplementasikannya menggunakan kode. Dan karena Anda berada di situs ini, saya berani menebak Anda menulis dalam bahasa Java. Oleh karena itu, hari ini saya mengajak Anda untuk membiasakan diri dengan beberapa algoritma dasar dan contoh spesifik implementasinya di Java. Yang saya maksud dengan beberapa hal adalah:

1. Ikhtisar algoritma pengurutan array:
   • semacam gelembung,
   • pengurutan pilihan,
   • semacam penyisipan,
   • Sortir cangkang,
   • penyortiran cepat,
   • menggabungkan semacam.
2. Algoritma serakah.
3. Algoritma pencarian jalan:
   • merangkak secara mendalam
   • jalan lebar.
4. Algoritma transportnya adalah algoritma Dijkstra.

Baiklah, tanpa basa-basi lagi, mari kita mulai bisnisnya.

1. Ikhtisar algoritma pengurutan

Sortir gelembung

Algoritme pengurutan ini terkenal terutama karena kesederhanaannya, namun pada saat yang sama memiliki salah satu kecepatan eksekusi terendah. Sebagai contoh, pertimbangkan pengurutan gelembung untuk angka-angka dalam urutan menaik. Mari kita bayangkan sebuah rangkaian angka yang ditempatkan secara acak dan langkah-langkah berikut akan dilakukan, dimulai dari awal rantai:

• bandingkan dua angka;
• jika angka di sebelah kiri lebih besar, tukarkan;
• pindah satu posisi ke kanan.

Setelah menelusuri seluruh rantai dan melakukan langkah-langkah ini, kita akan menemukan bahwa bilangan terbesar ada di akhir rangkaian bilangan kita. Selanjutnya, lintasan yang sama persis di sepanjang rantai dilakukan, mengikuti langkah-langkah yang dijelaskan di atas. Namun kali ini kami tidak akan memasukkan elemen terakhir dari daftar, karena ini adalah yang terbesar dan sudah berada di urutan terakhir, sebagaimana mestinya. Sekali lagi, kita akan mendapatkan elemen terakhir di akhir rangkaian angka yang dimaksud. Dengan demikian, dua angka terbesar sudah ada di tempatnya. Dan sekali lagi perjalanan sepanjang rantai dimulai, tidak termasuk elemen-elemen yang sudah ada, sampai semua elemen berada dalam urutan yang diperlukan. Mari kita lihat implementasi bubble sort dalam kode 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;
             }
         }
       }
   }
}

Seperti yang Anda lihat, tidak ada yang rumit di sini, dan semuanya tampak baik-baik saja, jika bukan karena satu "tetapi"... Bubble sort sangat, sangat lambat, dengan kompleksitas waktu O(N²) , karena kita telah membuat sarang loop. Pelarian eksternal melalui elemen dilakukan dalam N kali, yang internal juga N kali, dan sebagai hasilnya kita mendapatkan iterasi N*N , N² . Anda dapat mempelajari jenis penyortiran ini lebih detail di artikel ini .

Menyortir berdasarkan pilihan

Algoritma ini mirip dengan bubble sort, namun bekerja sedikit lebih cepat. Sekali lagi, sebagai contoh, mari kita ambil rangkaian angka yang ingin kita susun dalam urutan menaik. Inti dari algoritma ini adalah menelusuri semua angka secara berurutan dan memilih elemen terkecil, yang kita ambil dan menukar tempatnya dengan elemen paling kiri (elemen 0). Di sini kita mendapatkan situasi yang mirip dengan bubble sort, tetapi dalam kasus ini elemen yang diurutkan akan menjadi yang terkecil. Oleh karena itu, lintasan elemen berikutnya akan dimulai dengan elemen pada indeks 1. Sekali lagi, lintasan ini akan diulangi hingga semua elemen terurut. Implementasi di Jawa:

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;
       }
   }
}

Algoritme ini lebih unggul daripada bubble sort, karena di sini jumlah permutasi yang diperlukan dikurangi dari O(N²) menjadi O(N): kita tidak memasukkan satu elemen ke seluruh daftar, namun demikian, jumlah perbandingannya tetap O(N² ) . Bagi mereka yang ingin mempelajari lebih lanjut tentang algoritma ini, saya merekomendasikan materi ini .

Sortir penyisipan

Sekali lagi, sebagai contoh, mari kita ambil rangkaian angka yang ingin kita susun secara menaik. Algoritme ini terdiri dari penempatan penanda, di sebelah kiri elemen-elemen tersebut sudah diurutkan sebagian di antara mereka sendiri. Pada setiap langkah algoritma, salah satu elemen akan dipilih dan ditempatkan pada posisi yang diinginkan dalam urutan yang sudah diurutkan. Jadi bagian yang diurutkan akan terus bertambah hingga semua elemennya terlihat. Anda mungkin bertanya: di mana saya bisa mendapatkan bagian dari elemen yang sudah diurutkan dan setelah itu Anda perlu memberi penanda? Tapi array elemen pertama sudah diurutkan, bukan? Mari kita lihat implementasinya di 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;   // вставляем отмеченный элемент, в положеное ему место
       }
   }
}

Jenis pengurutan ini lebih unggul daripada yang dijelaskan di atas, karena meskipun waktu berjalannya sama - O(N²) , algoritma ini bekerja dua kali lebih cepat dari pengurutan gelembung dan sedikit lebih cepat dari pengurutan pilihan. Baca selengkapnya di sini .

Jenis cangkang

Pengurutan ini, pada dasarnya, adalah pengurutan penyisipan yang dimodifikasi. Apa yang saya bicarakan? Ayo berangkat secara berurutan. Sebuah langkah dipilih, dan ada banyak pendekatan terhadap pilihan ini. Kami tidak akan membahas masalah ini terlalu detail. Mari kita bagi array kita menjadi dua dan dapatkan angka tertentu - ini akan menjadi langkah kita. Jadi, jika kita memiliki 9 elemen dalam array, maka langkah kita adalah 9/2 = 4.5 . Kami membuang bagian pecahan dan mendapatkan 4 , karena indeks array hanya bilangan bulat. Dengan langkah ini kami akan membuat koneksi untuk grup kami. Jika suatu elemen memiliki indeks 0, maka indeks elemen berikutnya dalam grupnya adalah 0+4 , yaitu 4 . Elemen ketiga akan memiliki indeks 4+4 , elemen keempat akan memiliki indeks 8+4 , dan seterusnya. Untuk kelompok kedua, elemen pertama adalah 1,5,9…. Pada kelompok ketiga dan keempat, keadaannya akan sama persis. Hasilnya, dari deretan bilangan {6,3,8,8,6,9,4,11,1} kita peroleh empat golongan: I - {6,6,1} II - {3,9} III - {8, 4} IV - {8,11} Mereka mempertahankan tempatnya di susunan umum, tapi bagi kami mereka ditandai sebagai anggota grup yang sama: { 6 , 3 , 8 , 8 , 6 , 9 , 4 , 11 , 1 } Selanjutnya di dalam kelompok ini terjadi penyisipan seperti , setelah itu kelompok akan terlihat seperti: I - {1,6,6} II - {3,9} III - {4,8} IV - {8 ,11} Dalam larik umum, sel yang ditempati oleh grup , akan tetap sama, namun urutan di dalamnya akan berubah, sesuai dengan urutan grup di atas: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Susunannya sedikit lebih teratur, bukan? Langkah selanjutnya akan dibagi 2: 4/2 = 2 Kita punya dua grup: I - {1,4,6,8,6} II - {3,8,9,11} B array umum: { 1 , 3 , 4 , 8 , 6 , 9 , 8 , 11 , 6 } Kita menelusuri kedua grup menggunakan algoritma pengurutan penyisipan dan mendapatkan array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8} Sekarang array kita hampir terurut. Iterasi terakhir algoritma tetap ada: kita membagi langkah dengan 2: 2/2 = 1. Kita mendapatkan grup, keseluruhan array: { 1 , 3 , 4 , 8 , 6 , 9 , 6 , 11 , 8 } Oleh yang kita lalui algoritma pengurutan penyisipan dan dapatkan : { 1 , 3 , 4 , 6 , 6 , 8 , 8 , 9 , 11 } Mari kita lihat bagaimana kita dapat menampilkan pengurutan ini dalam kode 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; // уменьшаем наш шаг
       }
   }
}

Saat ini, efektivitas penyortiran Shell belum benar-benar terbukti, karena hasilnya berbeda-beda dalam berbagai situasi. Perkiraan yang diperoleh dari eksperimen berkisar dari O(N ^3/2 ) hingga O(N ^7/6 ) .

Penyortiran cepat

Ini adalah salah satu algoritma yang paling populer, dan oleh karena itu perlu mendapat perhatian khusus. Inti dari algoritme ini adalah elemen pivot dipilih dari daftar elemen—pada dasarnya elemen apa pun yang nilai sisanya perlu diurutkan. Nilai yang lebih kecil dari yang ada di sebelah kiri, nilai yang lebih besar dari yang ada di sebelah kanan. Selanjutnya bagian kanan dan kiri juga dipilih elemen pendukungnya dan terjadi hal yang sama: nilai-nilai diurutkan relatif terhadap elemen tersebut, kemudian elemen pendukung dipilih dari bagian yang dihasilkan - begitu seterusnya hingga kita mendapatkan hasil yang terurut. baris. Algoritma di Java ini diimplementasikan menggunakan rekursi:

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);
   }
}

Tidak diragukan lagi, algoritma quicksort dianggap yang paling populer, karena dalam kebanyakan situasi algoritma ini berjalan lebih cepat daripada yang lain, dalam waktu O(N*logN) .

Gabungkan semacam

Penyortiran ini juga populer. Ini mengacu pada salah satu jenis algoritme yang bekerja berdasarkan prinsip “membagi dan menaklukkan”: di dalamnya kita pertama-tama membagi tugas menjadi bagian-bagian minimal ( pengurutan cepat juga merupakan perwakilan dari algoritme tersebut ). Jadi, apa inti dari algoritma ini?

Membagi:

Array tersebut dibagi menjadi dua bagian yang kira-kira berukuran sama, masing-masing dari dua bagian tersebut dibagi menjadi dua bagian lagi, dan seterusnya hingga tersisa bagian terkecil yang tidak dapat dibagi lagi. Bagian terkecil yang tidak dapat dibagi adalah ketika setiap larik memiliki satu elemen, yang berarti larik tersebut secara otomatis dianggap terurut.

Menaklukkan:

Di sinilah proses yang memberi nama pada algoritma tersebut dimulai - penggabungan . Untuk melakukan ini, ambil dua array terurut yang dihasilkan dan gabungkan menjadi satu. Dalam hal ini, elemen terkecil pertama dari dua larik ditulis ke larik yang dihasilkan, dan operasi ini diulangi hingga tidak ada lagi elemen dalam dua larik. Artinya, jika kita memiliki dua array minimal {6} dan {4} , nilainya akan dibandingkan dan hasilnya akan ditulis: {4,6} . Jika ada array yang diurutkan {4,6} dan {2,8} , maka nilai 4 dan 2 akan dibandingkan terlebih dahulu , yang mana 2 akan ditulis ke array yang dihasilkan. Setelah itu, 4 dan 8 akan dibandingkan , 4 akan dituliskan, dan pada akhirnya 6 dan 8 akan dibandingkan . Oleh karena itu, 6 akan ditulis, dan hanya setelah itu - 8. Hasilnya, kita akan mendapatkan array yang dihasilkan: {2,4,6,8} . Bagaimana tampilannya dalam kode Java? Untuk memproses algoritma ini, akan lebih mudah bagi kita untuk menggunakan rekursi:

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;
   }
}

Seperti pada quick sort, kita memindahkan metode rekursif ke metode perantara sehingga pengguna tidak perlu repot mengatur argumen default tambahan, namun cukup menentukan array yang perlu diurutkan. Karena algoritme ini mirip dengan penghapusan yang lebih cepat, kecepatan eksekusinya sama - O(N*logN) .

2. Algoritma Serakah

Algoritma serakah adalah pendekatan yang mengambil keputusan optimal secara lokal pada setiap tahap dan mengasumsikan bahwa solusi akhir juga akan optimal. Solusi “optimal” adalah solusi yang menawarkan manfaat paling jelas dan langsung pada langkah/tahapan tertentu. Untuk mempertimbangkan algoritme ini, kami akan memilih masalah yang cukup umum - tentang ransel. Mari kita berpura-pura sejenak bahwa Anda adalah seorang pencuri. Anda masuk ke sebuah toko pada malam hari dengan membawa ransel, dan di depan Anda ada sejumlah barang yang bisa Anda curi. Namun pada saat yang sama, kapasitas ransel terbatas - tidak lebih dari 30 unit konvensional. Pada saat yang sama, Anda ingin membawa satu set barang dengan nilai maksimal yang dapat dimasukkan ke dalam ransel Anda. Bagaimana Anda memutuskan apa yang akan dimasukkan? Jadi, algoritma serakah untuk masalah knapsack terdiri dari langkah-langkah berikut (kami berasumsi bahwa semua objek masuk ke dalam knapsack):

1. Pilihlah barang yang paling mahal dari yang belum disentuh.
2. Jika muat di ransel Anda, taruh di sana; jika tidak, lewati saja.
3. Sudahkah Anda memilah semua item? Kalau belum kita kembali ke point 1, kalau iya kita lari dari toko, karena tujuan kita disini sudah selesai.

Mari kita lihat ini, tapi di Jawa. Seperti inilah tampilan kelas Item:

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;
   }
}

Tidak ada yang istimewa di sini: tiga bidang - nama , berat , biaya - untuk menentukan karakteristik barang. Selain itu, seperti yang Anda lihat, antarmuka Comparable diterapkan di sini sehingga kita dapat mengurutkan Item berdasarkan harga. Selanjutnya kita lihat kelas ransel kita - Tas :

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 adalah kapasitas ransel kita, yang diatur saat membuat objek;
• item — benda di dalam ransel;
• currentWeight , currentCost - berat saat ini dan biaya semua barang di ransel, yang kami tingkatkan saat menambahkan item baru dalam metode addItem .

Sebenarnya, mari kita masuk ke kelas, tempat semua aksi terjadi:

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());
}
}

Pertama, kita membuat daftar elemen dan mengurutkannya. Buatlah objek tas dengan kapasitas 30 unit. Selanjutnya, kami mengirimkan elemen dan objek tas ke metode fillBackpack , yang sebenarnya ransel diisi menggunakan algoritma serakah:

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

Semuanya sangat sederhana: kita mulai memeriksa daftar barang yang diurutkan berdasarkan biaya dan memasukkannya ke dalam tas, jika kapasitas memungkinkan. Jika tidak memungkinkan, elemen tersebut akan dilewati dan penelusuran elemen yang tersisa akan berlanjut hingga akhir daftar. Dengan menjalankan main, kita mendapatkan output berikut ke konsol: Sebenarnya, ini adalah contoh algoritma serakah: pada setiap langkah, solusi optimal lokal dipilih, dan pada akhirnya Anda mendapatkan solusi optimal global. Dalam kasus kami, pilihan terbaik adalah barang yang paling mahal. Namun apakah ini solusi terbaik? Tidakkah menurut Anda kami dapat sedikit memodernisasi solusi kami sehingga kami dapat melengkapi ransel dengan total biaya yang lebih tinggi? Mari kita lihat bagaimana hal ini dapat dilakukan:

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());
       }
   }
}

Di sini pertama-tama kita menghitung rasio berat-harga untuk setiap item. Jadi, berapa harga satu unit barang tertentu? Dan berdasarkan nilai-nilai ini kami mengurutkan barang-barang kami dan menambahkannya ke tas kami. Ayo lari:

Bag secondBag = new Bag(30);

effectiveFillBackpack(secondBag, items);

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

Kami mendapatkan output ke konsol: Sedikit lebih baik, bukan? Algoritma serakah membuat pilihan optimal secara lokal pada setiap langkah dengan harapan bahwa solusi akhir juga akan optimal. Hal ini tidak selalu bisa dibenarkan, namun untuk banyak masalah, algoritma serakah memang memberikan solusi optimal. Kompleksitas waktu dari algoritma ini adalah O(N) , yang cukup bagus bukan? Nah, dengan begitu, bagian pertama artikel ini telah berakhir. Jika Anda tertarik dengan kelanjutan artikel yang akan membahas tentang grafik dan algoritma yang terkait dengannya, Anda dapat menemukannya di sini .