So Sánh Hiệu Suất Thuật Toán

from time import perf_counter

start = perf_counter()
for x in range(1001):
    for y in range(1001):
        for z in range(1001):
            if x + y + z == 1000 and x*x + y*y == z*z:
                print(f"x, y, z: {x}, {y}, {z}")
                
end = perf_counter()
print(f"Thời gian: {end - start:.4f} giây")

Kết Quả Thực Thi

x, y, z: 0, 500, 500
x, y, z: 200, 375, 425
x, y, z: 375, 200, 425
x, y, z: 500, 0, 500
Thời gian: 286.512 giây

Cải Tiến Thuật Toán

start = perf_counter()
for x in range(1001):
    for y in range(1001):
        z = 1000 - x - y
        if x*x + y*y == z*z:
            print(f"x, y, z: {x}, {y}, {z}")

end = perf_counter()
print(f"Thời gian: {end - start:.4f} giây")

Kết Quả Tối Ưu

x, y, z: 0, 500, 500
x, y, z: 200, 375, 425
x, y, z: 375, 200, 425
x, y, z: 500, 0, 500
Thời gian: 0.812 giây

Khái Niệm Thuật Toán

Thuật toán là phương pháp giải quyết vấn đề độc lập với ngôn ngữ lập trình.

Đặc Tính Cơ Bản:

• Đầu vào xác định
• Đầu ra rõ ràng
• Tính hữu hạn
• Tính xác định
• Tính khả thi

Đo Lường Hiệu Suất

Độ phức tạp thời gian biểu thị số lượng thao tác cơ bản:

T1 = O(n³)
T2 = O(n²)

Chỉ xét số mũ cao nhất, bỏ qua hệ số hằng số.

Phân Loại Độ Phức Tạp:

• Trường hợp tốt nhất
• Trường hợp xấu nhất
• Trường hợp trung bình

Phân Tích Hiệu Suất Trong Python

from timeit import Timer

def test_concatenate():
    result = []
    for i in range(10000):
        result = result + [i]

def test_append():
    result = []
    for i in range(10000):
        result.append(i)

# Các phương pháp khác: list comprehension, constructor, extend, insert

timer = Timer("test_concatenate()", globals=globals())
print("Nối list:", timer.timeit(1000))

timer = Timer("test_append()", globals=globals())
print("Append:", timer.timeit(1000))

Kết Quả So Sánh

Nối list: 1.92 giây
Append: 0.48 giây
List comprehension: 0.31 giây
Hàm tạo: 0.15 giây
Extend: 0.87 giây
Insert: 41.85 giây

Cấu Trúc Dữ liệu

Mô tả quan hệ tĩnh giữa các phần tử dữ liệu. Chương trình = Cấu trúc dữ liệu + Thuật toán.

Kiểu dữ liệu trừu tượng (ADT) bao gồm cách tổ chức dữ liệu và các thao tác hỗ trợ.