Độ phức tạp thời gian trong Python là gì?

Đây là một bài viết về độ phức tạp của thời gian trong lập trình Python. Trong đó, chúng tôi khám phá ý nghĩa của độ phức tạp thời gian và cho thấy cùng một chương trình có thể hiệu quả hơn hoặc kém hơn đáng kể về mặt thời gian thực hiện tùy thuộc vào thuật toán được sử dụng

Các chủ đề được đề cập

• Độ phức tạp về thời gian trong lập trình Python là gì?
• Ký hiệu “O lớn”
• Vẽ biểu đồ độ phức tạp của thời gian với pyplot

Độ phức tạp của thời gian là một chủ đề mà nhiều lập trình viên tự học chưa học Khoa học máy tính có xu hướng né tránh. Tuy nhiên, rất đáng để nỗ lực tìm hiểu ít nhất những điều cơ bản của chủ đề này vì nó sẽ cho phép bạn viết mã hiệu quả hơn nhiều

Chủ đề về Độ phức tạp của thời gian trong lập trình thoạt đầu có vẻ hơi khó khăn với một số ký hiệu toán học không quen thuộc và các biểu đồ khác nhau được sử dụng để biểu thị thời gian hoàn thành thuật toán tăng lên như thế nào khi kích thước đầu vào của nó tăng lên

Tuy nhiên

Khái niệm cơ bản về độ phức tạp của thời gian là đơn giản. nhìn biểu đồ thời gian thực hiện trên trục y được vẽ theo kích thước đầu vào trên trục x, chúng tôi muốn giữ chiều cao của các giá trị y càng thấp càng tốt khi chúng tôi di chuyển dọc theo trục x

Bạn có thể hiểu rõ về độ phức tạp của thời gian bằng trực giác bằng cách nghiên cứu đồ thị của các hàm toán học khác nhau và chiều cao của đồ thị tăng lên như thế nào khi chúng ta di chuyển dọc theo trục x. Biểu đồ dưới đây cho thấy các loại hàm toán học khác nhau hoạt động như thế nào. Ý tưởng là thời gian thực hiện của các thuật toán có thể tăng theo kiểu tương tự với một trong các hàm loại này, tùy thuộc vào việc thực hiện nó. Mục tiêu của chúng tôi là viết các thuật toán hoạt động giống như các hàm phát triển chậm hơn và tránh các triển khai hoạt động giống như các hàm phát triển nhanh

Có rất nhiều chi tiết mà bạn có thể xem xét về việc chúng tôi đang xem xét trường hợp tốt nhất, trường hợp xấu nhất, trường hợp trung bình, v.v., nhưng đó thường là chi tiết hơn mức bạn cần. Để đơn giản, hãy nói

• số mũ. rất tệ
• hình khối. xấu, tránh nếu có thể
• bậc hai. xấu, tránh nếu có thể
• tuyến tính. tốt
• logarit. Tuyệt
• không thay đổi. bạn trúng số độc đắc

Ký hiệu Big O là một cách để chỉ các loại tăng trưởng này

• O[2ⁿ]. số mũ
• O[n³]. hình khối
• O[n²]. bậc hai
• Trên]. tuyến tính
• O[logn]. logarit
• Ô[1]. không thay đổi

Sách được đề xuất để học thuật toán và cấu trúc dữ liệu

Xin lưu ý, với tư cách là Cộng tác viên của Amazon, tôi kiếm được từ các giao dịch mua đủ điều kiện

Trong phần còn lại của bài viết này, thay vì tập trung vào lý thuyết chung về độ phức tạp của thời gian, chúng ta sẽ xem xét một thuật toán cụ thể đếm các phần tử phổ biến trong một danh sách

Hãy nhìn vào biểu đồ này

Bạn có thể thấy rõ ràng trên biểu đồ thời gian thực hiện của count_common_elements_nested_loops[] tăng nhanh hơn nhiều so với của count_common_elements_sets[]

nó sử dụng pyplot từ matplotlib, một thư viện vẽ sơ đồ mạnh mẽ cho Python. Chi tiết về cách sử dụng pyplot dành cho một bài viết khác, nhưng bằng cách kiểm tra mã bên dưới, bạn có thể hiểu được cách thức hoạt động của nó. Đoạn mã sử dụng perf_counter từ thư viện time để tính toán thời gian thực hiện của các thuật toán khác nhau để thực hiện nhiệm vụ đếm các phần tử chung là một danh sách. Bạn có thể thấy từ biểu đồ kết quả rằng có sự khác biệt đáng kể giữa các lần triển khai về độ phức tạp của thời gian khi kích thước của đầu vào cho mỗi chức năng tăng lên

Ví dụ về độ phức tạp của thời gian Danh sách mã Python

import random
import time
import matplotlib.pyplot as plt

MAX_LEN = 200  # Maximum length of input list.


def count_common_elements_nested_loops[l1, l2]:
    common_elements = []
    count = 0
    for v in l1:
        for w in l2:
            if w == v:
                common_elements.append[w]
                count += 1
    return count


def count_common_elements_list_comp[l1, l2]:
    common_elements = [x for x in l1 if x in l2]
    return len[common_elements]


def count_common_elements_sets[l1, l2]:
    common_elements = set[l1].intersection[l2]
    return len[common_elements]


def count_common_elements_hash_table[l1, l2]:
    table = {}
    common_elements = []
    for v in l1:
        table[v] = True
    count = 0
    for w in l2:
        if table.get[w]:  # Avoid KeyError that would arise with table[w]
            common_elements.append[w]
            count += 1
    return count


if __name__ == "__main__":

    # Initialise results containers
    lengths_nested = []
    times_nested = []
    lengths_comp = []
    times_comp = []
    lengths_hash_table = []
    times_hash_table = []
    lengths_sets = []
    times_sets = []

    for length in range[0, MAX_LEN, 10]:
        # Generate random lists
        l1 = [random.randint[0, 99] for _ in range[length]]
        l2 = [random.randint[0, 99] for _ in range[length]]

        # Time execution for nested lists version
        start = time.perf_counter[]
        count_common_elements_nested_loops[l1, l2]
        end = time.perf_counter[]

        # Store results
        lengths_nested.append[length]
        times_nested.append[end - start]

        # Time execution for list comprehension version
        start = time.perf_counter[]
        count_common_elements_list_comp[l1, l2]
        end = time.perf_counter[]

        # Store results
        lengths_comp.append[length]
        times_comp.append[end - start]

        # Time execution for hash table version
        start = time.perf_counter[]
        count_common_elements_hash_table[l1, l2]
        end = time.perf_counter[]

        # Store results
        lengths_hash_table.append[length]
        times_hash_table.append[end - start]

        # Time execution for sets version
        start = time.perf_counter[]
        count_common_elements_sets[l1, l2]
        end = time.perf_counter[]

        # Store results
        lengths_sets.append[length]
        times_sets.append[end - start]

    # Plot results
    plt.style.use["dark_background"]
    plt.figure[].canvas.manager.set_window_title["Common List Elements Algorithm - Time Complexity"]
    plt.xlabel["List Length"]
    plt.ylabel["Execution Time [s]"]
    plt.plot[lengths_nested, times_nested, label="count_common_elements_nested_loops[]"]
    plt.plot[lengths_comp, times_comp, label="count_common_elements_list_comp[]"]
    plt.plot[lengths_hash_table, times_hash_table, label="count_common_elements_hash_table[]"]
    plt.plot[lengths_sets, times_sets, label="count_common_elements_sets[]"]
    plt.legend[]
    plt.tight_layout[]
    plt.show[]

Một số quan sát

• Sự khác biệt về hiệu suất là rất đáng chú ý, đặc biệt là với tốc độ tăng trưởng của phiên bản vòng lặp for lồng nhau…
• Bạn có thể mong đợi việc hiểu danh sách có độ phức tạp về thời gian tương tự như các vòng for lồng nhau, vì khả năng hiểu danh sách có thể được tạo bằng các vòng for lồng nhau. Tuy nhiên, việc triển khai hiểu danh sách “dưới mui xe” hiệu quả hơn nhiều
• Điều tương tự cũng áp dụng cho các bộ so với hash_tables, vì các bộ sử dụng hash_tables. Tuy nhiên, Bộ. phương pháp giao cắt thực hiện trong C. Điều đáng ghi nhớ là nhiều hàm/phương thức tích hợp hầu như sẽ luôn nhanh hơn các thuật toán tương đương được thực thi ở cấp trình thông dịch python

Bài viết này nhằm cung cấp cho bạn trải nghiệm thực tế về cách làm việc với độ phức tạp về thời gian trong Python như một phần giới thiệu về chủ đề này. Độ phức tạp của thời gian là một chủ đề lớn và có rất nhiều tài nguyên có sẵn để giúp bạn học trực tuyến. Một nơi bạn có thể thực hành là trên các trang web như hackerrank và dự án euler, nơi cách tiếp cận “brute force” có thể đưa ra câu trả lời đúng, nhưng không đúng trong khung thời gian yêu cầu

Độ phức tạp thời gian và Python ví dụ là gì?

Độ phức tạp thời gian với ví dụ là gì?

Độ phức tạp thời gian là gì?

Độ phức tạp về thời gian và độ phức tạp về không gian trong Python là gì?