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

Đoạn mã trên nhận một số làm đối số và bắt đầu vòng lặp for, trong đó bạn chia lần lượt cho mọi số từ 2 đến số đó và kiểm tra phần dư. Nếu không có phần dư, bạn biết số đó không phải là số nguyên tố và lập tức trả về False. Nếu bạn đi hết đến số đó mà luôn có phần dư, thì số đó là số nguyên tố và bạn trả về True.

Bạn có thể xác định hiệu quả của thuật toán trên là O(N). Ví dụ trên không nhận dữ liệu dạng mảng hay danh sách mà số được truyền vào làm đối số. Nếu bạn truyền một số bất kỳ như 11, vòng lặp for chạy khoảng mười một bước. (Thực tế là chín bước, vì bắt đầu từ 2 và dừng ngay trước số đó.) Với số 101, vòng lặp chạy khoảng 101 bước. Vì số bước tăng tương ứng với số được truyền vào hàm, đây là ví dụ kinh điển của O(N).

def twoForLoops(n):
    for i in range(1,n):
        print("Printing:"+i);
    for i in range(1,100):
        print("Printing:"+i);

Trong đoạn mã trên, độ phức tạp của thuật toán là O(N). Vì vòng lặp thứ hai có đối số là 100, có thể bỏ qua vì bạn biểu diễn độ phức tạp với giả định N rất lớn.

def twoConditionalLoops(m,n):
    for i in range(0,m):
        print("Printing:"+i);
    for i in range(0,n):
        print("Printing:"+i);

Có hai vòng lặp, một vòng có độ dài m và vòng còn lại có độ dài n. Đồng thời, giả sử m và n đều lớn, khi đó độ phức tạp là O(n+m). Vì các vòng lặp khác nhau và nhận đầu vào khác nhau, độ phức tạp có tính cộng.

def twoNestedForLoops(int m,int n):
    for i in range(0,n):
        for j in range(0,m):
            print("Printing:"+(i*j));

Có một vòng lặp lồng nhau và lại giả sử n và m lớn, khi đó độ phức tạp là O(n*m). Vì các vòng lặp giống nhau và được lồng vào nhau, độ phức tạp có tính nhân.

Chúc mừng!

Bạn đã đi đến cuối hướng dẫn này! Trên hành trình, bạn đã học về ký hiệu tiệm cận cũng như một công cụ cơ bản được lập trình viên và nhà khoa học dữ liệu sử dụng. Bạn vừa học một cách đơn giản để phân tích độ phức tạp, được trình bày bằng ngôn ngữ giản dị, không quá nặng về thuật ngữ hay công thức. Dù chủ đề cấu trúc dữ liệu và thuật toán thường chỉ được đọc và dạy nếu bạn học ngành khoa học máy tính hoặc lĩnh vực liên quan, thì việc có kiến thức cơ bản về chủ đề này cũng rất quan trọng, dù không cần là chuyên gia. Để đào sâu hơn, bạn có thể tham khảo liên kết này: Khóa học Thuật toán trên MIT OpenCourseWare

Nếu bạn muốn học thêm về Python, hãy xem các khóa học của DataCamp dưới đây:

Chủ đề

PythonPhân tích dữ liệu

Liên quan

Xem thêm →