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

Artikel ini merupakan kelanjutan dari ulasan singkat saya tentang algoritma. Ini tautan ke bagian pertama . Sebelumnya, kita melihat berbagai algoritma pengurutan array dan apa yang disebut algoritma serakah . Hari ini kita akan berbicara tentang grafik dan algoritma yang terkait dengannya. Grafik adalah salah satu struktur paling fleksibel dan universal dalam pemrograman. Graf G biasanya ditentukan menggunakan sepasang himpunan G = (V, R) , dimana:

• V adalah himpunan simpul;
• R adalah himpunan garis yang menghubungkan pasangan simpul.

Garis penghubung yang umum disebut rusuk : Garis dengan panah - busur : Biasanya, suatu graf direpresentasikan menggunakan diagram yang beberapa simpulnya dihubungkan oleh rusuk (busur). Grafik yang dihubungkan satu sama lain oleh busur yang secara langsung menunjukkan arah disebut berarah . Jika grafik-grafik tersebut dihubungkan oleh sisi-sisinya, yaitu tanpa menunjukkan arah kemungkinan pergerakannya, maka grafik-grafik tersebut menjadi tidak berarah . Artinya, pergerakan sepanjang titik tersebut dimungkinkan dalam dua arah: baik dari titik A ke B, maupun dari B ke A. Graf terhubung adalah graf yang paling sedikit ada satu jalur yang mengarah dari setiap titik ke titik lainnya (seperti pada contoh). di atas ). Jika hal ini tidak terjadi, grafik menjadi tidak terhubung : Selain itu, sisi (busur) dapat diberi bobot - angka yang mewakili jarak fisik antara dua simpul (atau waktu transisi relatif antara dua simpul). Grafik seperti ini disebut berbobot :

3. Algoritma pencarian jalur (kedalaman, lebar)

Salah satu operasi dasar yang dilakukan pada graf adalah menentukan semua simpul yang dapat dijangkau dari suatu simpul tertentu. Bayangkan Anda mencoba menentukan cara berpindah dari satu kota ke kota lain dengan kemungkinan transfer. Beberapa kota dapat dicapai secara langsung, sementara kota lainnya memerlukan jalan memutar melalui kota lain. Ada banyak situasi lain di mana Anda mungkin perlu menemukan semua simpul yang jalurnya dapat Anda temukan dari simpul tertentu. Jadi, ada dua cara utama untuk melintasi grafik: traversal kedalaman-pertama dan traversal lebar-pertama , yang akan kita pertimbangkan. Kedua metode akan memastikan perulangan pada semua simpul yang terhubung. Untuk pertimbangan lebih lanjut tentang algoritma depth-first dan breadth-first , ambil grafik berikut:

Traversal Pertama Kedalaman

Ini adalah salah satu metode traversal grafik yang paling umum. Strategi pencarian depth -first ini terdiri dari masuk “jauh” ke dalam grafik sejauh mungkin, dan setelah mencapai jalan buntu, kembali ke simpul terdekat yang memiliki simpul-simpul tetangga yang belum pernah dikunjungi sebelumnya. Algoritma ini menyimpan informasi pada tumpukan tentang ke mana harus kembali ketika kebuntuan tercapai. Aturan untuk traversal kedalaman pertama:

1. Kunjungi titik yang berdekatan dan belum pernah dikunjungi sebelumnya, tandai dan letakkan di tumpukan.
2. Pergi ke titik ini.
3. Ulangi langkah 1.
4. Jika langkah 1 tidak dapat diselesaikan, kembalilah ke simpul sebelumnya dan coba ulangi aturan 1. Jika tidak mungkin, kembalilah ke simpul sebelumnya, dan seterusnya, hingga kita menemukan simpul yang dapat kita lanjutkan penjelajahannya.
5. Lanjutkan sampai semua simpul berada di tumpukan.

Mari kita lihat seperti apa tampilan kode algoritma ini di Java:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexArray[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Stack<integer> stack;

  public Graph() { // инициализация внутрених полей
     vertexArray = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {
           adjMat[j][k] = 0;
        }
     }
     stack = new Stack<>();
  }

  public void addVertex(char lab) {
     vertexArray[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexArray[v].getLabel());
  }

  public void dfs() { // обход в глубину
     vertexArray[0].setWasVisited(true); // берётся первая вершина
     displayVertex(0);
     stack.push(0);

     while (!stack.empty()) {
        int v = getAdjUnvisitedVertex(stack.peek()); // вынуть индекс смежной веришины, еckи есть 1, нету -1
        if (v == -1) { // если непройденных смежных вершин нету
           stack.pop(); // элемент извлекается из стека
        }
        else {
           vertexArray[v].setWasVisited(true);
           displayVertex(v);
           stack.push(v); // элемент попадает на вершину стека
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexArray[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexArray[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Bagian atasnya terlihat seperti:

public class Vertex {
  private char label;  // метка А например
  public boolean wasVisited;

  public Vertex(final char label) {
     this.label = label;
     wasVisited = false;
  }

  public char getLabel() {
     return this.label;
  }

  public boolean isWasVisited() {
     return this.wasVisited;
  }

  public void setWasVisited(final boolean wasVisited) {
     this.wasVisited = wasVisited;
  }
}

Mari kita jalankan algoritme ini dengan simpul tertentu dan lihat apakah algoritme berfungsi dengan benar:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.dfs();
  }
}

Keluaran konsol: Karena kita memiliki matriks ketetanggaan dan dalam metode walk kita menggunakan perulangan yang bersarang di dalam perulangan, kompleksitas waktunya adalah O(N²) .

Berjalan lebar

Algoritme ini, seperti depth-first traversal, adalah salah satu metode paling sederhana dan mendasar untuk melintasi suatu grafik. Esensinya adalah bahwa kita memiliki simpul tertentu saat ini, dari mana kita memasukkan semua simpul yang berdekatan dan belum dilintasi ke dalam antrian dan memilih elemen berikutnya (yang disimpan pertama dalam antrian) untuk menjadikannya yang terkini... Jika kita memecah algoritma ini menjadi tahapannya, kita dapat menyoroti aturan berikut:

1. Kunjungi simpul berikutnya yang belum pernah dikunjungi sebelumnya, berdekatan dengan simpul saat ini, tandai terlebih dahulu dan tambahkan ke antrian.
2. Jika aturan #1 tidak dapat dipenuhi, hapus simpul tersebut dari antrian dan jadikan simpul tersebut sebagai simpul saat ini.
3. Jika aturan #1 dan #2 tidak mungkin dilakukan, traversal selesai dan semua simpul telah dilintasi (jika graf kita terhubung).

Kelas grafik hampir identik dengan kelas serupa dari algoritma pencarian depth-first, dengan pengecualian metode yang memproses algoritma dan menggantikan tumpukan internal dengan antrian:

public class Graph {
  private final int MAX_VERTS = 10;
  private Vertex vertexList[]; //массив вершин
  private int adjMat[][]; // матрица смежности
  private int nVerts; // текущее количество вершин
  private Queue<integer> queue;

  public Graph() {
     vertexList = new Vertex[MAX_VERTS];
     adjMat = new int[MAX_VERTS][MAX_VERTS];
     nVerts = 0;
     for (int j = 0; j < MAX_VERTS; j++) {
        for (int k = 0; k < MAX_VERTS; k++) {  // заполнение матрицы смежности нулями
           adjMat[j][k] = 0;
        }
     }
     queue = new PriorityQueue<>();
  }

  public void addVertex(char lab) {
     vertexList[nVerts++] = new Vertex(lab);
  }

  public void addEdge(int start, int end) {
     adjMat[start][end] = 1;
     adjMat[end][start] = 1;
  }

  public void displayVertex(int v) {
     System.out.println(vertexList[v].getLabel());
  }

  public void bfc() { // обход в глубину
     vertexList[0].setWasVisited(true);
     displayVertex(0);
     queue.add(0);
     int v2;

     while (!queue.isEmpty()) {
        int v = queue.remove();

        while((v2 = getAdjUnvisitedVertex(v))!=-1) {// цикл будет работать, пока все смежные вершины не будут найденны, и не будут добавлены в очередь
           vertexList[v2].wasVisited =true;
           displayVertex(v2);
           queue.add(v2);
        }
     }

     for (int j = 0; j < nVerts; j++) {  // сброс флагов
        vertexList[j].wasVisited = false;
     }

  }

  private int getAdjUnvisitedVertex(int v) {
     for (int j = 0; j < nVerts; j++) {
        if (adjMat[v][j] == 1 && vertexList[j].wasVisited == false) {
           return j; //возвращает первую найденную вершину
        }
     }
     return -1;
  }
}
</integer>

Kelas Vertex identik dengan kelas dari algoritma pencarian depth-first . Mari kita terapkan algoritma ini:

public class Solution {
  public static void main(String[] args) {
     Graph graph = new Graph();
     graph.addVertex('A'); //0
     graph.addVertex('B'); //1
     graph.addVertex('C'); //2
     graph.addVertex('D'); //3
     graph.addVertex('E'); //4
     graph.addVertex('F'); //5
     graph.addVertex('G'); //6

     graph.addEdge(0,1);
     graph.addEdge(0,2);
     graph.addEdge(0,3);
     graph.addEdge(1,4);
     graph.addEdge(3,5);
     graph.addEdge(5,6);

     System.out.println("Visits: ");
     graph.bfc();
  }
}

Keluaran konsol: Sekali lagi: kita memiliki matriks ketetanggaan dan menggunakan perulangan yang bersarang di dalam perulangan, jadi O(N²) adalah kompleksitas waktu dari algoritma di atas.

4. Algoritma Dijkstra

Seperti yang telah disebutkan sebelumnya, grafik dapat berarah atau tidak berarah . Dan seperti yang Anda ingat, mereka masih bisa ditimbang . Grafik berbobot dan berarah sering ditemukan dalam kehidupan nyata: misalnya, peta kota, di mana kota-kota tersebut adalah simpul, jalur di antara mereka adalah jalan raya, jalan dapat memiliki lalu lintas satu arah - arah grafik. Katakanlah Anda bergerak di bidang transportasi kargo dan Anda perlu membuat rute terpendek antara dua kota yang berjauhan. Bagaimana kamu akan melakukan ini? Salah satu permasalahan paling umum yang melibatkan graf berbobot adalah permasalahan pemilihan jalur terpendek antara dua simpul. Untuk menyelesaikan masalah ini kami menggunakan algoritma Dijkstra . Saya ingin segera mencatat bahwa dengan menjalankan algoritma Dijkstra kita akan menemukan jalur terpendek ke semua simpul dari titik awal tertentu. Tahapan apa yang dimiliki algoritma ini? Saya akan mencoba menjawab pertanyaan ini. Tahapan algoritma Dijkstra :

• Tahap 1 : mencari node, transisi ke mana yang biayanya paling murah. Anda berdiri di awal dan bertanya-tanya ke mana harus pergi: ke simpul A atau ke simpul B. Berapa lama waktu yang dibutuhkan untuk mencapai masing-masing node tersebut?
• Tahap 2 : menghitung berapa lama waktu yang diperlukan untuk mencapai semua tetangga B yang belum terpengaruh oleh algoritma ketika bergerak sepanjang tepi dari B. Jika waktu baru ini ternyata lebih kecil dari waktu lama, maka jalur yang melalui sisi B akan menjadi jalur terpendek baru untuk titik tersebut.
• Tahap 3 : menandai titik B sebagai dilewati.
• Langkah 4 : Lanjutkan ke Langkah 1.

Kami akan mengulangi siklus tahapan ini sampai semua puncak telah dilewati. Mari kita perhatikan grafik berarah berbobot berikut ini: Jadi, dengan menggunakan algoritma di atas, kita akan menentukan jalur terpendek dari A ke G:

1. Untuk simpul A ada tiga kemungkinan jalur: ke B dengan bobot 3, ke C dengan bobot 5, dan ke D dengan bobot 7. Menurut poin pertama algoritme, kami memilih simpul dengan transisi terendah biaya - yaitu, ke B.
2. Karena satu-satunya simpul tetangga yang belum dilintasi untuk B adalah simpul E , kita periksa jalur apa yang akan dilalui ketika melewati simpul ini. 3( AB ) + 6( MENJADI ) = 9.

   Jadi, kami mencatat bahwa jalur terpendek saat ini menuju AE = 9.

3. Karena pekerjaan kita dengan simpul B telah selesai, kita melanjutkan ke pemilihan simpul berikutnya dengan bobot minimum dari sisi sebelumnya.

   Dari simpul A dan B dapat menjadi simpul D (7), C (5), E (6).

   C mempunyai bobot tepi terkecil , jadi kita beralih ke simpul ini.

4. Selanjutnya, seperti sebelumnya, kita mencari jalur terpendek ke simpul tetangga ketika melewati C:
   • AD = 5( AC ) + 3( CD ) = 8, tetapi karena jalur terpendek sebelumnya AC = 7, yaitu kurang dari jalur ini yang melalui C , kita membiarkan jalur terpendek AD = 7 tidak berubah.
   • CE = 5( AC ) + 4( CE ) = 9, jalur terpendek baru ini sama dengan yang sebelumnya jadi kita biarkan saja tidak berubah.
5. Dari simpul-simpul terdekat yang tersedia, E dan D , kita pilih simpul yang mempunyai bobot sisi terkecil, yaitu D (3).
6. Kami menemukan jalur terpendek ke tetangganya - F.

   AF = 7( IKLAN ) + 3( DF ) = 10

7. Dari simpul-simpul terdekat yang tersedia E dan F , kita pilih simpul yang mempunyai bobot sisi paling kecil, yaitu F (3).
8. Kami menemukan jalur terpendek ke tetangganya - G.

   AG = 7( IKLAN ) + 3( DF ) + 4( FG ) = 14

   Sebenarnya di sini kita telah menemukan jalan dari A ke G.

   Namun untuk memastikan bahwa ini adalah yang terpendek, kita harus menjalankan langkah-langkah kita untuk titik E juga .

9. Karena simpul G tidak memiliki simpul-simpul tetangga yang akan dituju oleh suatu jalur berarah, kita hanya mempunyai simpul E yang tersisa : kita memilihnya.
10. Kami menemukan jalur terpendek ke tetangga - G.

    AG = 3( AB ) + 6( BE ) + 6( EG ) = 15, jalur ini lebih panjang dari AG(14) terpendek sebelumnya, jadi jalur ini tidak diubah.

    Karena tidak ada simpul yang mengarah dari G , maka tidak masuk akal untuk menjalankan tahapan untuk simpul tertentu. Oleh karena itu, kerja algoritma dapat dianggap selesai.

Seperti yang saya katakan sebelumnya, selain mencari jalur terpendek untuk AG , kami juga mendapatkan jalur terpendek ke semua simpul dari simpul A (AB, AC, AD, AE, AF) . Sekarang saatnya melihat bagaimana hal ini dapat diterapkan di Java. Pertama, mari kita lihat kelas vertex:

public class Vertex {
   private char label;
   private boolean isInTree;

   public Vertex(char label) {
       this.label = label;
       this.isInTree = false;
   }

   public char getLabel() {
       return label;
   }

   public void setLabel(char label) {
       this.label = label;
   }

   public boolean isInTree() {
       return isInTree;
   }

   public void setInTree(boolean inTree) {
       isInTree = inTree;
   }
}

Kelas vertex sebenarnya identik dengan kelas vertex dari pencarian depth-first dan broadth-first. Untuk menampilkan jalur terpendek, kita memerlukan kelas baru yang berisi data yang kita perlukan:

public class Path { // an object данного класса содержащий расстояние и предыдущие и пройденные вершины
   private int distance; // текущая дистанция от начальной вершины
   private List<integer> parentVertices; // текущий родитель вершины

   public Path(int distance) {
       this.distance = distance;
       this.parentVertices = new ArrayList<>();
   }

   public int getDistance() {
       return distance;
   }

   public void setDistance(int distance) {
       this.distance = distance;
   }

   public List<integer> getParentVertices() {
       return parentVertices;
   }

   public void setParentVertices(List<integer> parentVertices) {
       this.parentVertices = parentVertices;
   }
}
</integer></integer></integer>

Pada kelas ini kita dapat melihat total jarak lintasan dan simpul yang akan ditempuh jika melewati lintasan terpendek. Dan sekarang saya ingin mempertimbangkan kelas di mana, pada kenyataannya, traversal terpendek dari grafik tersebut terjadi. Jadi, kelas grafiknya:

public class Graph {
   private final int MAX_VERTS = 10;// максимальное количество вершин
   private final int INFINITY = 100000000; // это число у нас будет служить в качестве "бесконечности"
   private Vertex vertexList[]; // список вершин
   private int relationMatrix[][]; // матрица связей вершин
   private int countOfVertices; // текущее количество вершин
   private int countOfVertexInTree; // количество рассмотренных вершин в дереве
   private List<path> shortestPaths; // список данных кратчайших путей
   private int currentVertex; // текущая вершина
   private int startToCurrent; //расстояние до currentVertex

   public Graph() {
       vertexList = new Vertex[MAX_VERTS]; // матрица смежности
       relationMatrix = new int[MAX_VERTS][MAX_VERTS];
       countOfVertices = 0;
       countOfVertexInTree = 0;
       for (int i = 0; i < MAX_VERTS; i++) {// матрица смежности заполняется
           for (int k = 0; k < MAX_VERTS; k++) { // бесконечными расстояниями
               relationMatrix[i][k] = INFINITY; // задания значений по умолчанию
               shortestPaths = new ArrayList<>();// задается пустым
           }
       }
   }

   public void addVertex(char lab) {// задание новых вершин
       vertexList[countOfVertices++] = new Vertex(lab);
   }

   public void addEdge(int start, int end, int weight) {
       relationMatrix[start][end] = weight; // задание ребер между вершинами, с весом между ними
   }

   public void path() { // выбор кратчайшего пути
       //  задание данных для стартовой вершины
       int startTree = 0; // стартуем с вершины 0
       vertexList[startTree].setInTree(true); // включение в состав дерева первого element
       countOfVertexInTree = 1;

       // заполнение коротких путей для вершин смежных с стартовой
       for (int i = 0; i < countOfVertices; i++) {
           int tempDist = relationMatrix[startTree][i];
           Path path = new Path(tempDist);
           path.getParentVertices().add(0);// первым родительским элементом, будет всегда стартовая вершина
           shortestPaths.add(path);
       }
       // пока все вершины не окажутся в дереве
       while (countOfVertexInTree < countOfVertices) { // выполняем, пока количество вершин в дереве не сравняется с общим количеством вершин
           int indexMin = getMin();//получаем индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
           int minDist = shortestPaths.get(indexMin).getDistance();// минимальная дистанция вершины, из тек которые ещё не в дереве

           if (minDist == INFINITY) {
               System.out.println("В графе пристувствуют недостижимые вершины");
               break;// в случае если остались непройденными только недостижимые вершины, мы выходим из цикла
           } else {
               currentVertex = indexMin; // переводим указатель currentVert к текущей вершине
               startToCurrent = shortestPaths.get(indexMin).getDistance();// задаем дистанцию к текущей вершине
           }

           vertexList[currentVertex].setInTree(true);  //включение текущей вершины в дерево
           countOfVertexInTree++; // увеличиваем счетчик вершин в дереве
           updateShortestPaths(); // обновление списка кратчайших путей
       }

       displayPaths(); // выводим в консоль результаты
   }

   public void clean() { // очиска дерева
       countOfVertexInTree = 0;
       for (int i = 0; i < countOfVertices; i++) {
           vertexList[i].setInTree(false);
       }
   }

   private int getMin() {
       int minDist = INFINITY; // за точку старта взята "бесконечная" длина
       int indexMin = 0;
       for (int i = 1; i < countOfVertices; i++) {// для каждой вершины
           if (!vertexList[i].isInTree() && shortestPaths.get(i).getDistance() < minDist) { // если вершина ещё не ве дереве и её растояние меньше старого минимума
               minDist = shortestPaths.get(i).getDistance(); // задаётся новый минимум
               indexMin = i; // обновление индекса вершины содержащую минимаьную дистанцию
           }
       }
       return indexMin; //возвращает индекс вершины с наименшей дистанцией, из вершин еще не входящих в дерево
   }

   private void updateShortestPaths() {
       int vertexIndex = 1; // стартовая вершина пропускается
       while (vertexIndex < countOfVertices) { // перебор столбцов

           if (vertexList[vertexIndex].isInTree()) { // если вершина column уже включена в дерево, она пропускается
               vertexIndex++;
               continue;
           }
           // вычисление расстояния для одного element sPath
           // получение ребра от currentVert к column
           int currentToFringe = relationMatrix[currentVertex][vertexIndex];
           // суммирование всех расстояний
           int startToFringe = startToCurrent + currentToFringe;
           // определение расстояния текущего element vertexIndex
           int shortPathDistance = shortestPaths.get(vertexIndex).getDistance();

           // сравнение расстояния через currentVertex с текущим расстоянием в вершине с индексом vertexIndex
           if (startToFringe < shortPathDistance) {// если меньше, то у вершины под индексом vertexIndex будет задан новый кратчайший путь
               List<integer> newParents = new ArrayList<>(shortestPaths.get(currentVertex).getParentVertices());//создаём копию списка родителей вершины currentVert
               newParents.add(currentVertex);// задаём в него и currentVertex How предыдущий
               shortestPaths.get(vertexIndex).setParentVertices(newParents); // соохраняем новый маршут
               shortestPaths.get(vertexIndex).setDistance(startToFringe); // соохраняем новую дистанцию
           }
           vertexIndex++;
       }
   }

   private void displayPaths() { // метод для вывода кратчайших путей на экран
       for (int i = 0; i < countOfVertices; i++) {
           System.out.print(vertexList[i].getLabel() + " = ");
           if (shortestPaths.get(i).getDistance() == INFINITY) {
               System.out.println("0");
           } else {
               String result = shortestPaths.get(i).getDistance() + " (";
               List<integer> parents = shortestPaths.get(i).getParentVertices();
               for (int j = 0; j < parents.size(); j++) {
                   result += vertexList[parents.get(j)].getLabel() + " -> ";
               }
               System.out.println(result + vertexList[i].getLabel() + ")");
           }
       }
   }
}
</integer></integer></path>

Sebenarnya, itu saja keajaibannya =) Sekarang, mari kita lihat cara kerja algoritma ini:

public class Solution {

   public static void main(String[] args) {
       Graph graph = new Graph();
       graph.addVertex('A');
       graph.addVertex('B');
       graph.addVertex('C');
       graph.addVertex('D');
       graph.addVertex('E');
       graph.addVertex('F');
       graph.addVertex('G');

       graph.addEdge(0, 1, 3);
       graph.addEdge(0, 2, 5);
       graph.addEdge(0, 3, 7);
       graph.addEdge(1, 4, 6);
       graph.addEdge(2, 4, 4);
       graph.addEdge(2, 3, 3);
       graph.addEdge(3, 5, 3);
       graph.addEdge(4, 6, 6);
       graph.addEdge(5, 6, 4);

       System.out.println("Элементы имеют кратчайшие пути из точки A: ");
       graph.path();
       graph.clean();
   }
}

Dan output di konsol: Kompleksitas waktu dari algoritma ini tidak lebih dari O(N²) karena kita memiliki loop yang bersarang di dalam satu loop. Baiklah, itu saja untuk saya hari ini, terima kasih atas perhatiannya!