Chuyển đến nội dung chính

Phân tích độ phức tạp của mã bằng Python

Làm quen với Phân tích Tiệm cận. Tìm hiểu thêm về độ phức tạp của thuật toán cũng như ký hiệu tiệm cận như Big O, Big θ và Big Ω. Kèm theo các ví dụ về độ phức tạp trong các thuật toán khác nhau.
· 11 phút đọc

Khám phá cùng AI

Độ phức tạp của một thuật toán là thước đo lượng thời gian và/hoặc bộ nhớ mà thuật toán cần cho một đầu vào có kích thước cho trước (n). Mặc dù độ phức tạp của thuật toán phụ thuộc vào các yếu tố cụ thể như: kiến trúc máy tính (tức nền tảng phần cứng), cách biểu diễn Kiểu Dữ liệu Trừu tượng (ADT), hiệu quả của trình biên dịch, độ phức tạp của thuật toán nền tảng, kích thước đầu vào. Tuy nhiên, bạn sẽ thấy các yếu tố quan trọng nhất là độ phức tạp của thuật toán nền tảng và kích thước đầu vào.

Trong bài viết trên blog của DataCamp Python Data Structures Tutorial, bạn có thể tìm hiểu tổng quan cơ bản về cấu trúc dữ liệu và cách triển khai cấu trúc dữ liệu trong Python. Bài viết giới thiệu về các cấu trúc dữ liệu cơ bản của Python. Qua đó, bạn sẽ khám phá Kiểu Dữ liệu Trừu tượng và Cấu trúc Dữ liệu, Cấu trúc Dữ liệu Nguyên thủy và Phi nguyên thủy.

Phân tích tiệm cận

Phân tích tiệm cận đề cập đến việc tính thời gian chạy của bất kỳ đoạn mã hay thao tác nào theo đơn vị toán học của một phép tính. Thời gian chạy được biểu diễn theo một hàm như f(n). Trong phân tích toán học, phân tích tiệm cận (asymptotics) là phương pháp mô tả hành vi giới hạn.

Thời gian cần thiết của thuật toán thường được xét theo ba loại: Trường hợp xấu nhất - Thời gian tối đa mà thuật toán cần, và thường được sử dụng khi phân tích thuật toán. Trường hợp tốt nhất - Thời gian tối thiểu cho thuật toán hoặc đoạn mã, và thường không được tính khi phân tích. Trường hợp trung bình - Thời gian trung bình cho thuật toán hoặc đoạn mã, đôi khi được xét khi phân tích.

Ký hiệu tiệm cận

Các ký hiệu thường dùng để tính độ phức tạp thời gian chạy của thuật toán như sau:

  • Ký hiệu Big O
  • Ký hiệu Big θ
  • Ký hiệu Big Ω

Ký hiệu Big Oh, Ο

Big O được dùng để đo lường hiệu năng hoặc độ phức tạp của một thuật toán. Ở dạng toán học hơn, đó là cận trên của tốc độ tăng trưởng của một hàm, nghĩa là nếu một hàm g(x) không tăng nhanh hơn một hàm f(x), thì g được xem là phần tử của O(f). Nói chung, nó dùng để biểu diễn cận trên của một thuật toán và cho biết độ phức tạp thời gian tệ nhất, hay khoảng thời gian dài nhất mà một thuật toán có thể cần để hoàn tất.

Ký hiệu Big Omega, Ω

Ký hiệu Ω(n) là cách thức chính quy để biểu diễn cận dưới của thời gian chạy thuật toán. Nó đo lường độ phức tạp thời gian tốt nhất, tức khoảng thời gian ít nhất mà một thuật toán có thể cần để hoàn tất.

Ký hiệu Big Theta, θ

Ký hiệu θ(n) là cách thức chính quy để biểu diễn cả cận dưới và cận trên của thời gian chạy thuật toán.

Ký hiệu dùng để xác định độ phức tạp của các thuật toán khác nhau

Ký hiệu Big O được dùng nhiều nhất, chủ yếu để tìm cận trên của một thuật toán; trong khi ký hiệu Big θ đôi khi được dùng để phát hiện trường hợp trung bình; còn ký hiệu Ω là ít được dùng nhất trong ba loại.

Bạn sẽ xem các ví dụ về ký hiệu được dùng trong thuật toán để xác định độ phức tạp của thuật toán đó.

Ví dụ với quick sort:

Quick sort là thuật toán Chia để Trị dùng cho việc sắp xếp. Nó là một phương pháp có hệ thống để đặt các phần tử theo thứ tự, ví dụ: sắp xếp các phần tử hay số trong mảng theo thứ tự tăng dần hoặc giảm dần. Thuật toán này chọn pivot (điểm trụ) hay chỉ số được chọn từ mảng cho trước. Pivot có thể được chọn theo nhiều cách khác nhau. Ví dụ triển khai dưới đây chọn phần tử cuối làm pivot.

Cốt lõi của Quick sort là phép chia mảng (partition). Từ một mảng, chọn một phần tử làm phần tử chia, sau đó đặt phần tử chia (ví dụ pit) vào vị trí đúng của nó; các phần tử lớn hơn phần tử chia đặt bên phải pit, và các phần tử nhỏ hơn đặt bên trái pit.

#The last element will be taken as a pivot by the use of the function
#The smaller element is placed left to the pivot
#The greater element is placed to the right of the pivot
def partition(array,low,high):
    i = ( low-1 )         # index of smaller element is chosen
    pivot = array[high]     # pivot is chosen

    for j in range(low , high):

        #Is the element less or equal to the pivot
        if   array[j] <= pivot:

            # increment index of smaller element
            i = i+1
            array[i],array[j] = array[j],array[i]

    array[i+1],array[high] = array[high],array[i+1]
    return ( i+1 )

# The main crux of the problem that implements Quick sort is
#array[] is to be sorted
#high is the ending index
#low is the starting index

# Function to do Quick sort
def quickSort(array,low,high):
    if low < high:

       #pit is the partitioning index
        pit = partition(array,low,high)

      #Element sorted before and after partition
        quickSort(array, low, pit-1)
        quickSort(array, pit+1, high)

array=[2,4,6,8,10,12]
n = len(array)
quickSort(array,0,n-1)
print ("The Sorted array is:")
for i in range(n):
    print ("%d" %array[i]),

Mảng đã được sắp xếp là:
2
4
6
8
10
12
Bạn sẽ nhận được đầu ra:

Mảng đã được sắp xếp là: 2 4 6 8 10 12

Bây giờ là lúc phân tích độ phức tạp thời gian. Trước hết,

  • Trường hợp tốt nhất: Ω(n log(n))
  • Trường hợp trung bình: Θ(n log(n))
  • Trường hợp xấu nhất: O(n^2)

Giờ hãy phân tích đoạn mã trên.

Trường hợp tốt nhất: Đây là khi phần tử chia chọn phần tử ở giữa làm pivot. Vì thuật toán sẽ đệ quy trên nửa đầu và nửa sau, tổng số bước cần thiết là số lần cần để đi từ n về 1 nếu mỗi bước bạn chia vấn đề cho 2. Vậy có n/2/2/2/2/..../2=1 trong k lần. Lưu ý phương trình thực tế là: n / 2^k = 1. Vì 2^logn = n, ta được k = log n. Vậy số bước (số vòng lặp) thuật toán cần là O(log n), và thuật toán thành O(n log n) vì mỗi vòng lặp là O(n).

Trường hợp trung bình: Để tính trung bình, cần xét tất cả các hoán vị của mảng và tính thời gian cho mỗi hoán vị. Bạn có thể tham khảo thêm tại Merge sort.

Trường hợp xấu nhất: Trong xấu nhất, nếu phần tử đầu tiên được chọn làm pivot, độ phức tạp xấu nhất xảy ra khi đầu vào cần sắp xếp đã theo thứ tự tăng hoặc giảm. Lý do là sau khi phân hoạch, một bên sẽ có kích thước 1 và bên còn lại có kích thước n-1. Khi đó, T(n) là hàm: Thời gian quick sort n phần tử T(n) = Thời gian phân hoạch n phần tử O(n) + Thời gian quick sort n-1 phần tử T(n-1). Vậy T(n) = T(n-1) + O(n) => T(n) = O(n^2)

Ví dụ

Đoạn mã dưới đây có thể không “đẹp” và bạn có thể không gọi nó là thuật toán, nhưng về mặt kỹ thuật, bất kỳ đoạn mã nào làm được việc gì đó đều là một thuật toán và là cách giải một vấn đề cụ thể. Thuật toán bạn thấy dưới đây dùng vòng lặp for chứa một lệnh in duy nhất.

print('I love Python');

Xin chào thế giới!
Độ phức tạp thời gian của thuật toán trên là O(1) vì nó luôn chỉ mất một bước. Đây là thời gian hằng.

stuffs= ['eggs','toothbrush','kittens','mugs']
for stuff in stuffs:
    print("Here's a stuff: {}".format(stuff));

Here's a stuff: eggs Here's a stuff: toothbrush Here's a stuff: kittens Here's a stuff: mugs Bạn sẽ mô tả hiệu quả của thuật toán trên theo ký hiệu Big O như thế nào?

Để phân tích thuật toán trên, bạn cần xem xét số bước mà thuật toán thực hiện. Ở ví dụ trên, danh sách có bốn phần tử và bạn cần in mỗi phần tử một lần. Nhưng hãy nghĩ nếu danh sách có nhiều hơn 4 phần tử, ví dụ 15 phần tử, thì vòng lặp for có mất cùng số bước cho 15 phần tử không? Vì vòng lặp for này thực hiện số bước tỷ lệ với số phần tử, bạn cần nói rằng thuật toán có hiệu năng O(N) thay vì O(1).

Ví dụ tiếp theo là một thuật toán Python đơn giản để xác định một số có phải là số nguyên tố hay không:

def is_prime(number):   
    for i in range(2, number):       
        if number % 2 == 0:           
            return True   
    return False