Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Merge Sort, sau đây campusstudylab.vn sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Merge Sort thông qua các phần sau.You watching: độ phức tạp của thuật toán merge sort

1.

Bạn đang xem: Độ phức tạp của thuật toán merge sort

Giới thiệu

Giống như QuickSort, Merge Sort là một thuật toán Chia và Chinh phục. Nó chia mảng đầu vào thành hai nửa, gọi chính nó cho hai nửa và sau đó hợp nhất hai nửa đã sắp xếp. Hàm merge () được sử dụng để hợp nhất hai nửa. Hợp nhất (arr, l, m, r) là quá trình quan trọng giả định rằng arr và arr được sắp xếp và hợp nhất hai mảng con đã sắp xếp thành một. Xem cách triển khai C sau để biết thêm chi tiết.

MergeSort (arr , l, r)Nếu r> l 1. Tìm điểm giữa để chia mảng thành hai nửa: Ở giữa m = (l + r) / 2 2. Hợp nhất cuộc gọi Sắp xếp cho nửa đầu: Gọi mergeSort(arr, l, m) 3. Hợp nhất cuộc gọi Sắp xếp cho nửa sau: Gọi mergeSort(arr, m + 1, r) 4. Hợp nhất hai nửa được sắp xếp ở bước 2 và 3: Gọi merge(arr, l, m, r)Sơ đồ sau đây từ wikipedia cho thấy quy trình sắp xếp hợp nhất hoàn chỉnh cho một mảng ví dụ {38, 27, 43, 3, 9, 82, 10}. Nếu chúng ta xem xét kỹ hơn sơ đồ, chúng ta có thể thấy rằng mảng được chia đệ quy làm hai nửa cho đến khi kích thước trở thành 1. Khi kích thước trở thành 1, các quá trình hợp nhất sẽ hoạt động và bắt đầu hợp nhất các mảng trở lại cho đến khi mảng hoàn chỉnh đã hợp nhất.See more: Chú Đại Bi Có Ý Nghĩa Gì - Ý Nghĩa Của Từng Câu Trong Kinh Chú Đại Bi

Hình ảnh minh hoạ

2. Code ví dụ trên nhiều ngôn ngữ

C++

// C++ program for Merge Sort #include using namespace std; // Merges two subarrays of arr. // First subarray is arr // Second subarray is arr void merge(int arr, int l, int m, int r) { int n1 = m - l + 1; int n2 = r - m; // Create temp arrays int L, R; // Copy data to temp arrays L and R for(int i = 0; i C

/* C program for Merge Sort */#include #include // Merges two subarrays of arr. // First subarray is arr // Second subarray is arr void merge(int arr, int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* create temp arrays */ int L, R; /* Copy data to temp arrays L and R */ for (i = 0; i Java

/* Java program for Merge Sort */class MergeSort { // Merges two subarrays of arr. // First subarray is arr // Second subarray is arr void merge(int arr, int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 = m - l + 1; int n2 = r - m; /* Create temp arrays */ int L = new int; int R = new int; /*Copy data to temp arrays*/ for (int i = 0; i Python3

# Python program for implementation of MergeSort def mergeSort(arr): if len(arr) >1: mid = len(arr)//2 # Finding the mid of the array L = arr # Dividing the array elements R = arr # into 2 halves mergeSort(L) # Sorting the first half mergeSort(R) # Sorting the second half i = j = k = 0 # Copy data to temp arrays L and R while i Kết quả

Given array is12 11 13 5 6 7Sorted array is5 6 7 11 12 13

3.

Xem thêm: #4 Cách Đắp Mặt Nạ Lòng Trắng Trứng Mấy Lần 1 Tuần ? Làm Mặt Nạ Trứng Gà

Độ phức tạp

Độ phức tạp về thời gian: Sắp xếp các mảng trên các máy khác nhau. Merge Sort là một thuật toán đệ quy và độ phức tạp thời gian có thể được biểu thị như sau.See more: Ngày Thế Giới Phòng Chống Ung Thư Và Ngày Thế Giới Phòng Chống Ung Thư, 04

T (n) = 2T (n / 2) + θ (n)Sự lặp lại trên có thể được giải quyết bằng cách sử dụng phương pháp tree lặp lại hoặc phương pháp Master. Nó nằm trong trường hợp II của Phương pháp Master và nghiệm của sự tái diễn là θ (nLogn). Độ phức tạp thời gian của Sắp xếp hợp nhất(Merge Sort) là θ (nLogn) trong cả 3 trường hợp (xấu nhất, trung bình và tốt nhất) vì sắp xếp hợp nhất luôn chia mảng thành hai nửa và mất thời gian tuyến tính để hợp nhất hai nửa.

Không gian phụ trợ: O (n)

Mô hình thuật toán: Chia và Chinh phục

Ổn định: Có

4. Ứng dụng

Merge Sort rất hữu ích để sắp xếp các danh sách được liên kết trong thời gian O (nLogn). Trong trường hợp danh sách được liên kết, trường hợp này khác nhau chủ yếu do sự khác biệt trong phân bổ bộ nhớ của mảng và danh sách được liên kết. Không giống như mảng, các nút danh sách liên kết có thể không liền kề trong bộ nhớ. Không giống như một mảng, trong danh sách liên kết, chúng ta có thể chèn các mục vào giữa trong O (1) không gian thừa và O (1) thời gian. Do đó hoạt động hợp nhất của sắp xếp hợp nhất có thể được thực hiện mà không có thêm dung lượng cho danh sách được liên kết. Trong mảng, chúng ta có thể thực hiện truy cập ngẫu nhiên khi các phần tử nằm kề nhau trong bộ nhớ. Giả sử chúng ta có một mảng A số nguyên (4 byte) và đặt địa chỉ của A là x thì để truy cập A , chúng ta có thể truy cập trực tiếp vào bộ nhớ tại (x + i * 4). Không giống như mảng, chúng ta không thể thực hiện truy cập ngẫu nhiên trong danh sách liên kết. Sắp xếp nhanh yêu cầu rất nhiều loại truy cập. Trong danh sách liên kết để truy cập chỉ mục thứ i, chúng ta phải di chuyển từng nút từ đầu đến nút thứ i vì chúng ta không có khối bộ nhớ liên tục. Do đó, chi phí tăng đối với nhanh chóng. Sắp xếp hợp nhất truy cập dữ liệu một cách tuần tự và nhu cầu truy cập ngẫu nhiên thấp.Vấn đề đảo ngược số lượngĐược sử dụng trong sắp xếp bên ngoài

Nguồn và Tài liệu tiếng anh tham khảo:

Tài liệu từ campusstudylab.vn:

Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của campusstudylab.vn để nhận được nhiều hơn nữa: