Cấu trúc dữ liệu & giải thuật

Trần Đức Lĩnh

Cấu trúc dữ liệu + Giải thuật = Chương trình

Khi viết một chương trình, giải một bài toán dựa vào 2 yếu tố, lựa chọn cấu trúc dữ liệu cho phù hợp, tiếp theo tìm ra phương hướng kết hợp mọi thứ bằng giải thuật để có được bài toán đó.

Mục lục.

1) Độ phức tạp của thuật toán (big O)

Chính là độ nhanh hay chậm của thuật toán. Dựa vào tổn thời gian / số phép tính toán mà chương trình cần để thực hiện.

  • Big O: Chữ O là ký hiệu được sử dụng cho độ phức tạp thuật toán.

    • O(1) → O(log n) → O(n) → O(n log(n)) → O(n^2) → O(2^n) → O(!n)

image-title-here

Code.

sum = 0
for i in range(0, 10):
    sum = 2 * i
    print("2 *", i, '=', sum)

# 2 * 0 = 0
# 2 * 1 = 2
# 2 * 2 = 4
# 2 * 3 = 6
# 2 * 4 = 8
# 2 * 5 = 10
# 2 * 6 = 12
# 2 * 7 = 14
# 2 * 8 = 16
# 2 * 9 = 18

Xét chương trình ta có:

  • i = 0: được gán (1 lần)
  • i < 10: được gán (10 lần)
  • i ++: được tăng (10 lần)
  • 2 * i: được tính (10 lần)
  • sum =: được gán (10 lần)
  • print: được tính toán và gán giá trị (10 * 4) bao gồm print và 3 dấu phẩy ','

Lúc này => 8 * 10 + 1 = 81

Rút gọn biểu thức thành: 8 * n + 1


Định nghĩa: g(n) được gọi là O của f(n) nếu tồn tại C khi đó (>0, không phụ thuộc vào n) và n0 sao cho với mọi n > n0.

Biểu thức sẽ là: f(n) <= C.g(n)


image-title-here

Vậy:

  • 8 * n + 1 = f(n)
  • g(n) = n
  • C = 9
  • n0 = 1

Xét về mặt lý thuyết suy ra:

  • n > n0 vậy C.g(n) >= f(n)
  • n > 1 vậy 9.n >= 8 * n + 1

Trong đó g(n) = n chính là độ phức tạp của O(n).

O(1): Nếu chỉ sử dụng 1 bộ nhớ cố định.
O(2n): chính bằng O(n).

2) Sắp xếp

2.1) Sắp xếp nổi bọt (Bubble sort)

Độ phức tạp: O(n^2)

Code.

def bubble_sort(nums):
    indexing_lenth = range(len(nums) -1, 0, -1)
    for i in indexing_lenth:
        for j in range(i):
            if nums[j] > nums[j+1]:
                temp = nums[j]
                nums[j] = nums[j+1]
                nums[j+1] = temp

list_ = [3, 7, 5, 2]
bubble_sort(list_)

# [2, 3, 5, 7]

Sẽ có 2 vòng lặp:

  • Vòng lặp đầu tiên sẽ lặp giảm dần.
  • Vòng lặp thứ hai sẽ bắt cặp với chỉ số vòng lặp đầu tiên và chỉ số đó tăng lên 1, sau khi đã bắt cặp và sẽ swap nếu chỉ số trước lớn hơn chỉ số sau.

image-title-here

Cứ sau mỗi vòn lặp sẽ có 1 số vào đúng bị trí của nó.

Trường hợp xấu nếu vòng lặp đầu tiên không giảm mà vẫn giữ nguyên số vòng lặp.

Hoạt động hiệu quả đối với những array nhỏ.

2.2) Sắp xếp chèn (Insertion sort)

Độ phức tạp: O(n^2)

image-title-here

Code.

def insertion_sort(nums):
    indexing_lenth = range(1, len(nums))
    for i in indexing_lenth:
        position = nums[i]
        index = i - 1
        while index >= 0:
            if position < nums[index]:
                nums[index + 1] = nums[index]
                nums[index] = position
                index = index -1
            else:
                break

list_ = [3, 7, 5, 2, 4, 8]
insertion_sort(list_)

# [2, 3, 4, 5, 7, 8]

Thuật toán này sẽ bắt đầu với chỉ số từ [1] thay vì [0].

Từ vị trí bắt đầu làm chuẩn, trở về phía trái là đã sắp xếp, phía còn lại chưa sắp xếp.

Xem hình:

image-title-here

2.3) Sắp xếp chọn (Selection sort).

Độ phức tạp: O(n^2)

Trình tự thực hiện:

  • 0)Từ vị trí bắt đầu làm chuẩn, trở về phía trái là đã sắp xếp, phía còn lại chưa sắp xếp.
    1. Chọn phần tử đâu tiên của mảng làm giá trị nhỏ nhất.
    1. So sánh với giá trị kế tiếp cho đến hết mảng.
    2. 2.1) Nếu nhỏ hơn giá trị ban đầu ở bất cứ vị trí nào, bắt đầu gán biến tạm
    3. 2.2) Khi duyệt hết mảng, thoả điều kiện, bắt đầu swap.
    1. Xê dịch vị trí đầu tiên, lặp lại bước (1)

Code.

def selection_sort(nums):
    indexing_lenth = range(0, len(nums) - 1)
    for i in indexing_lenth:
        values = i
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[values]:
                values = j
            
        temp = nums[i]
        nums[i] = nums[values]
        nums[values] = temp


list_ = [3, 7, 5, 2, 0]
selection_sort(list_)

# [0, 2, 3, 5, 7]

Xem hình:

image-title-here

2.4) Sắp xếp trộn (Merge sort).

Độ phức tạp: O(n log (n))

Nhanh và tính ổn định cao vì cho dù trường hợp tốt hay xấu đều có độ phức tạp như nhau.

Tuy nhiên không gian lưu trữ bộ nhớ lại kém hiệu quả.

Dùng kỹ thuật chia để trị cho việc sắp xếp.

Hoạt động theo kiểu phân tách -> kết hợp.

Sử dụng đệ quy để gọi chính nó để triển khai thuật toán.

Điều kiện tiên quyết:

  • Cần xác định phần tử ở giữa array (tạm gọi là middle) để phân tách.

Sau khi xác định (middle) có độ dài là số lẻ, thì phần bên trái (L) sẽ nhiều hơn phần bên phải (R) 1 đơn vị.

image-title-here

Code.

def merge_sort(nums):

    if len(nums) <= 1:
        return nums

    middle = int(len(nums)/2)

    left, right = merge_sort(nums[:middle]), merge_sort(nums[middle:])

    return merge(left, right)

def merge (left, right):

    result = []

    L_pointer = R_pointer = 0

    while L_pointer < len(left) and R_pointer < len(right):
        
        if left[L_pointer] < right[R_pointer]:
            result.append(left[L_pointer])
            L_pointer += 1
        else:
            result.append(right[R_pointer])
            R_pointer += 1
        
    result.extend(left[L_pointer:])
    result.extend(right[R_pointer:])

    return result

def main():

    dict_ = [3, 7, 5, 2, 0, 4, 8]
    
    result = merge_sort(dict_)

    print(result)

if __name__ == '__main__':
    main()

Giải thích:

Hàm merge_sort() image-title-here

Hàm merge() image-title-here

2.5) Sắp xếp nhanh (Quick sort).

Độ phức tạp: O(n log (n))

Ý tưởng:

  • Bước (1): Cần xác định (Pivot), lấy item đầu tiên sắp xếp làm sao các item lớn nằm phía bên phải (R), các item bé hơn hoặc bằng nằm phía bên trái (L).
  • Bước (2): Sau khi đã xác định được (Pivot) và đưa và đúng vị trí trong mảng.
  • Bước (3): Tiếp theo phân mảng thành 3 vế gồm (L, Pivot, R).
  • Bước (4): Lặp lại bước (1) từ vế bên trái (L) trước. Sau đó mới tới vế bên phải (R).

Điều kiện tiên quyết:

  • Sử dụng đệ quy để xử lý bài toán.

image-title-here

Tiếp theo.

image-title-here

Giải thích cách xác định Pivot:

  • (1) Khi lấy item đầu tiên sẽ bằng với Pivot cũng là (L).
  • (2) So sánh với item cuối cùng của mảng sẽ là (R).
  • (3) Sau mỗi lần so sánh, kết quả trả về là true sẽ swap giữa (L) và (R) đồng thời tăng chỉ số vế (L) hoặc giảm chỉ số vế (R).
  • (4) So sánh cho đến khi (L)/(R) trùng nhau, đưa Pivot vào vị trí. (Hoàn thành việc xác định Pivot - phân mảnh)

Giải thích phần xử lý từng vế:

  • (1) Sau đó sẽ bắt đầu từ vế (L).
  • (2) Tiếp tục tìm Pivot vế bên (L).
  • (3) Sau khi hoàn thành tiếp tục phần (R) của vế bên (L).
  • (4) Lặp lại vế bên (R) như bước (1).

Code.

def swap (a, b, arr):
   if a!=b:
       temp = arr[a]
       arr[a] = arr[b]
       arr[b] = temp

def quick_sort (items, start, end):
   if start < end:
       pivot = partition(items, start, end)
       quick_sort(items, start, pivot-1)
       quick_sort(items, pivot+1, end)

def partition(items, start, end):
   pivote_intex = start
   pivot = items[pivote_intex]

   while start < end:
       while start < len(items) and items[start] <= pivot:
           start += 1
       
       while items[end] > pivot:
           end -= 1

       if start < end:
           swap(start, end, items)

   swap(pivote_intex, end, items)

   return end

if __name__ == '__main__':
   items = [ 3, 7, 5, 2, 4, 8 ]
   quick_sort(items, 0, len(items)-1)
   
   print(items)

   # [2, 3, 4, 5, 7, 8]

2.6) Sắp xếp vun đống (Heap sort).

Độ phức tạp: O(n log (n))

  • Thuật toán sắp xếp vun đống có gồm:

    • Build max heap
    • Build min heap

Thuật toán sắp xếp vung đống dựa có liên quan đến cây nhị phân.

image-title-here

Sự ưu tiên từ trên xuống và từ trái sang phải, mỗi nhánh chỉ có 2 node. Được phân bố liên tục không ngắt quãng. Những trường hợp không hợp lệ.

image-title-here

Đi vào thuật toán.

Cho một mảng gồm 7 phần tử được tính từ 1 đến 7, đồng thời là (size) của thuật toán. Phần tử đầu tiên bắt đầu từ 0 (cũng chính là chỉ số index).

Xác định vị trí.

    1. Last parent node (vị trí bắt đầu, được xác định lần build max/min heap lần đầu tiên) theo công thức:
    2. size/2-1 == n
    1. Parent node (vị trí phía trên của node đã xác định):
    2. (n-1)/2
    1. Left node (vị trí node con nằm phía bên trái):
    2. 2n+1
    1. Right node (vị trí node con nằm phía bên phải):
    2. 2n+2

image-title-here

Dựa vào công thức bài toán.

image-title-here

  • Last parent node: 7 / 2 - 1 = 2.5 lấy phần nguyên là 2.
  • Parent node: ( n - 1 ) / 2 = 0.5 lấy phần nguyên là 0.
  • Left node: 2 n + 1 = 5
  • Right node: 2 n + 2 = 6

Bắt đầu thực hiện bài toán.

  • Bước 1:

    • Đầu tiên từ vị trí Last parent node, so sánh giữa Left nodeRight node.
    • Nếu số nào lớn thì so sánh tiếp với Last parent node, thoả điều kiện thì thực hiện swap.

image-title-here

  • Bước 2:

    • Nhưng lưu ý, thuật toán sẽ luôn luôn kiểm trả toàn bộ phía Left node.
    • Nếu trả về undefined mới thực hiện swap.
    • Tiếp tục lùi về 1 chỉ số index, lúc này sẽ là Right node.

image-title-here

  • Bước 3:

    • Lúc này vị trí Last parent node sẽ ở vị trí index = 2 với giá trị bằng 7.
    • Tiếp tục so sánh Left nodeRight node, kiểm tra phần đẹ quy phía dưới Left nodeundefined, không có sự thay đổi.
    • Lúc này so sánh giữa 2 giá trị cùng mức - cấp bậc với nhau, thoả điều kiện, tiếp tục so sánh với root - parent.

image-title-here

  • Bước 4:

    • Sau khi build được max heap, bắt đầu swap rootindex cuối cùng của mảng.
    • Đồng thời loại bỏ index cuối cùng ra khỏi heap.

image-title-here

image-title-here

  • Bước 5: (Bước này tính toán khác so với ban đầu)

    • Bắt đầu từ vị trí root, so sánh giữa Left nodeRight node.
    • Nếu thoả điều kiện, so sánh với root sau đó thực hiện swap.
    • Tránh thuật toán sẽ gặp ra lỗi, tiếp tục kiểm tra toàn bộ các child phía dưới, đề phòng nếu child lớn hơn Last parent node, lập tức swap.

image-title-here

image-title-here

def max_heap(arr, length, parent_index):

    largest = parent_index
    left_node = 2 * parent_index + 1
    right_node = 2 * parent_index + 2

    if left_node < length and arr[left_node] > arr[largest]:

        largest = left_node

    if right_node < length and arr[right_node] > arr[largest]:

        largest = right_node

    if largest != parent_index:

        arr[largest], arr[parent_index] = arr[parent_index], arr[largest]
        max_heap(arr, length, largest)

def heap_sort(nums):
    
    length = len(nums)

    for i in range(length // 2 - 1, -1, -1): #Chia lay phan nguyen

        max_heap(nums, length, i)

    for i in range(length - 1, 0, -1):

        nums[i], nums[0] = nums[0], nums[i]
        max_heap(nums, i, 0)

lists = [3, 7, 5, 2, 4, 8, 6]
heap_sort(lists)
print(lists)

# [2, 3, 4, 5, 6, 7, 8]

(Còn nữa)