Giảm độ phức tạp về thời gian trong Python

Điều quan trọng đầu tiên là bạn chỉ cần kiểm tra i trong phạm vi(1, số/2). , vì số/2 + 1 trở lên không thể là thừa số.  

Thứ hai, bạn có thể tính số lượng ô vuông hoàn hảo có thể là nhân tố trong thời gian tuyến tính

hình vuông = []

cho tôi trong phạm vi (1, toán học. tầng (toán. sqrt(số/2)))

hình vuông. nối thêm (i**2)

Thứ ba, bạn có thể tìm kiếm các thừa số và khi bạn tìm thấy một thừa số, hãy lưu ý rằng nó không chia hết cho bình phương và thực sự lúc đó hãy thêm nó vào danh sách các thừa số

Ngày nay, với tất cả những dữ liệu này chúng ta tiêu thụ và tạo ra mỗi ngày, các thuật toán phải đủ tốt để xử lý các hoạt động với khối lượng dữ liệu lớn

Trong bài viết này, chúng ta sẽ hiểu thêm một chút về độ phức tạp của thời gian, ký hiệu Big-O và tại sao chúng ta cần quan tâm đến nó khi phát triển thuật toán

Các ví dụ hiển thị trong câu chuyện này được phát triển bằng Python, vì vậy sẽ dễ hiểu hơn nếu bạn có ít nhất kiến ​​thức cơ bản về Python, nhưng đây không phải là điều kiện tiên quyết

Hãy bắt đầu tìm hiểu độ phức tạp tính toán là gì

Độ phức tạp tính toán

Độ phức tạp tính toán là một lĩnh vực từ khoa học máy tính phân tích các thuật toán dựa trên lượng tài nguyên cần thiết để chạy nó. Lượng tài nguyên cần thiết thay đổi dựa trên kích thước đầu vào, do đó độ phức tạp thường được biểu thị dưới dạng hàm của n, trong đó n là kích thước của đầu vào

Điều quan trọng cần lưu ý là khi phân tích một thuật toán, chúng ta có thể xem xét độ phức tạp về thời gian và độ phức tạp về không gian. Độ phức tạp của không gian về cơ bản là dung lượng bộ nhớ cần thiết để giải quyết vấn đề liên quan đến kích thước đầu vào. Mặc dù độ phức tạp về không gian rất quan trọng khi phân tích một thuật toán, nhưng trong câu chuyện này, chúng ta sẽ chỉ tập trung vào độ phức tạp về thời gian

Thời gian phức tạp

Khi bạn đang đọc câu chuyện này ngay bây giờ, bạn có thể có ý tưởng về độ phức tạp của thời gian là gì, nhưng để đảm bảo rằng tất cả chúng ta đều ở trên cùng một trang, hãy bắt đầu tìm hiểu độ phức tạp của thời gian có nghĩa là gì với một mô tả ngắn từ Wikipedia

Trong khoa học máy tính, độ phức tạp thời gian là độ phức tạp tính toán mô tả khoảng thời gian cần thiết để chạy một thuật toán. Độ phức tạp về thời gian thường được ước tính bằng cách đếm số lượng thao tác cơ bản được thực hiện bởi thuật toán, giả sử rằng mỗi thao tác cơ bản cần một khoảng thời gian cố định để thực hiện

Khi phân tích độ phức tạp về thời gian của thuật toán, chúng ta có thể thấy ba trường hợp. trường hợp tốt nhất, trường hợp trung bình và trường hợp xấu nhất. Hãy hiểu ý nghĩa của nó

Giả sử chúng ta có danh sách chưa sắp xếp sau [1, 5, 3, 9, 2, 4, 6, 7, 8] và chúng ta cần tìm chỉ mục của một giá trị trong danh sách này bằng tìm kiếm tuyến tính

• trường hợp tốt nhất. đây là sự phức tạp của việc giải quyết vấn đề cho đầu vào tốt nhất. Trong ví dụ của chúng tôi, trường hợp tốt nhất là tìm kiếm giá trị 1. Vì đây là giá trị đầu tiên của danh sách nên nó sẽ được tìm thấy trong lần lặp đầu tiên
• trường hợp trung bình. đây là độ phức tạp trung bình của việc giải quyết vấn đề. Độ phức tạp này được xác định đối với sự phân bố của các giá trị trong dữ liệu đầu vào. Có thể đây không phải là ví dụ tốt nhất, nhưng dựa trên mẫu của chúng tôi, chúng tôi có thể nói rằng trường hợp trung bình sẽ xảy ra khi chúng tôi đang tìm kiếm một số giá trị ở “giữa” của danh sách, ví dụ: giá trị 2
• trường hợp xấu nhất. đây là độ phức tạp của việc giải quyết vấn đề đối với đầu vào tồi tệ nhất có kích thước n. Trong ví dụ của chúng ta, trường hợp xấu nhất là tìm kiếm giá trị 8, là phần tử cuối cùng trong danh sách

Thông thường, khi mô tả độ phức tạp về thời gian của một thuật toán, chúng ta đang nói về trường hợp xấu nhất

Ok, nhưng làm thế nào chúng ta mô tả độ phức tạp thời gian của một thuật toán?

Chúng tôi sử dụng một ký hiệu toán học gọi là Big-O

Ký hiệu Big-O

Ký hiệu Big-O, đôi khi được gọi là "ký hiệu tiệm cận", là một ký hiệu toán học mô tả hành vi giới hạn của một hàm khi đối số có xu hướng hướng tới một giá trị cụ thể hoặc vô cùng

Trong khoa học máy tính, ký hiệu Big-O được sử dụng để phân loại các thuật toán theo yêu cầu về thời gian hoặc không gian chạy của chúng tăng lên như thế nào khi kích thước đầu vào (n) tăng lên. Ký hiệu này đặc trưng cho các chức năng theo tốc độ tăng trưởng của chúng. các chức năng khác nhau có cùng tốc độ tăng trưởng có thể được biểu diễn bằng cùng một ký hiệu O

Hãy xem một số độ phức tạp thời gian phổ biến được mô tả trong ký hiệu Big-O

Bảng độ phức tạp thời gian phổ biến

Đây là những độ phức tạp thời gian phổ biến nhất được biểu thị bằng ký hiệu Big-O

╔══════════════════╦═════════════════╗
║       Name       ║ Time Complexity ║
╠══════════════════╬═════════════════╣
║ Constant Time    ║       O(1)      ║
╠══════════════════╬═════════════════╣
║ Logarithmic Time ║     O(log n)    ║
╠══════════════════╬═════════════════╣
║ Linear Time      ║       O(n)      ║
╠══════════════════╬═════════════════╣
║ Quasilinear Time ║    O(n log n)   ║
╠══════════════════╬═════════════════╣
║ Quadratic Time   ║      O(n^2)     ║
╠══════════════════╬═════════════════╣
║ Exponential Time ║      O(2^n)     ║
╠══════════════════╬═════════════════╣
║ Factorial Time   ║       O(n!)     ║
╚══════════════════╩═════════════════╝

Lưu ý rằng chúng tôi sẽ tập trung nghiên cứu của chúng tôi trong các độ phức tạp thời gian phổ biến này nhưng có một số phức tạp thời gian khác mà bạn có thể nghiên cứu sau

Như đã nói, chúng ta thường sử dụng ký hiệu Big-O để mô tả độ phức tạp về thời gian của thuật toán. Có rất nhiều phép toán liên quan đến định nghĩa chính thức của ký hiệu, nhưng một cách không chính thức, chúng ta có thể giả định rằng ký hiệu Big-O cho chúng ta thời gian chạy gần đúng của thuật toán trong trường hợp xấu nhất. Khi sử dụng ký hiệu Big-O, chúng tôi mô tả hiệu quả của thuật toán dựa trên kích thước ngày càng tăng của dữ liệu đầu vào (n). Ví dụ: nếu đầu vào là một chuỗi thì n sẽ là độ dài của chuỗi. Nếu nó là một danh sách, n sẽ là độ dài của danh sách, v.v.

Bây giờ, chúng ta hãy đi qua từng độ phức tạp thời gian phổ biến này và xem một số ví dụ về thuật toán. Lưu ý rằng tôi đã cố gắng làm theo cách tiếp cận sau. trình bày một chút mô tả, hiển thị một ví dụ đơn giản và dễ hiểu và hiển thị một ví dụ phức tạp hơn (thường là từ một vấn đề trong thế giới thực)

Thời gian phức tạp

Hằng số thời gian — O(1)

Một thuật toán được cho là có thời gian không đổi khi nó không phụ thuộc vào dữ liệu đầu vào (n). Bất kể kích thước của dữ liệu đầu vào, thời gian chạy sẽ luôn giống nhau. Ví dụ

if a > b:
    return True
else:
    return False

Bây giờ, hãy xem hàm get_first trả về phần tử đầu tiên của danh sách

def get_first(data):
    return data[0]
    
if __name__ == '__main__':
    data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
    print(get_first(data))

Không phụ thuộc vào kích thước dữ liệu đầu vào, nó sẽ luôn có cùng thời gian chạy vì nó chỉ nhận giá trị đầu tiên từ danh sách

Một thuật toán có độ phức tạp thời gian không đổi là tuyệt vời vì chúng ta không cần phải lo lắng về kích thước đầu vào

Thời gian logarit — O(log n)

Một thuật toán được cho là có độ phức tạp thời gian logarit khi nó giảm kích thước của dữ liệu đầu vào trong mỗi bước (không cần xem xét tất cả các giá trị của dữ liệu đầu vào), chẳng hạn

for index in range(0, len(data), 3):
    print(data[index])

Các thuật toán có độ phức tạp thời gian logarit thường được tìm thấy trong các hoạt động trên cây nhị phân hoặc khi sử dụng tìm kiếm nhị phân. Hãy cùng xem ví dụ về tìm kiếm nhị phân, trong đó chúng ta cần tìm vị trí của một phần tử trong danh sách đã sắp xếp

def binary_search(data, value):
    n = len(data)
    left = 0
    right = n - 1
    while left <= right:
        middle = (left + right) // 2
        if value < data[middle]:
            right = middle - 1
        elif value > data[middle]:
            left = middle + 1
        else:
            return middle
    raise ValueError('Value is not in the list')
    
if __name__ == '__main__':
    data = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    print(binary_search(data, 8))

Các bước tìm kiếm nhị phân

• Tính giữa danh sách
• Nếu giá trị được tìm kiếm thấp hơn giá trị ở giữa danh sách, hãy đặt giới hạn bên phải mới
• Nếu giá trị được tìm kiếm cao hơn giá trị ở giữa danh sách, hãy đặt giới hạn bên trái mới
• Nếu giá trị tìm kiếm bằng với giá trị ở giữa danh sách, hãy trả về phần giữa (chỉ mục)
• Lặp lại các bước trên cho đến khi giá trị được tìm thấy hoặc giới hạn bên trái bằng hoặc cao hơn giới hạn bên phải

Điều quan trọng là phải hiểu rằng một thuật toán phải truy cập tất cả các phần tử của dữ liệu đầu vào của nó không thể mất thời gian logarit, vì thời gian để đọc đầu vào có kích thước n là thứ tự của n

Thời gian tuyến tính — O(n)

Một thuật toán được cho là có độ phức tạp thời gian tuyến tính khi thời gian chạy tăng tuyến tính nhất với kích thước của dữ liệu đầu vào. Đây là độ phức tạp thời gian tốt nhất có thể khi thuật toán phải kiểm tra tất cả các giá trị trong dữ liệu đầu vào. Ví dụ

for value in data:
    print(value)

Hãy cùng xem ví dụ về tìm kiếm tuyến tính, trong đó chúng ta cần tìm vị trí của một phần tử trong danh sách chưa sắp xếp

def linear_search(data, value):
    for index in range(len(data)):
        if value == data[index]:
            return index
    raise ValueError('Value not found in the list')
    
if __name__ == '__main__':
    data = [1, 2, 9, 8, 3, 4, 7, 6, 5]
    print(linear_search(data, 7))

Lưu ý rằng trong ví dụ này, chúng ta cần xem xét tất cả các giá trị trong danh sách để tìm giá trị mà chúng ta đang tìm kiếm

Thời gian chuẩn tuyến tính — O(n log n)

Một thuật toán được cho là có độ phức tạp thời gian chuẩn tuyến tính khi mỗi thao tác trong dữ liệu đầu vào có độ phức tạp thời gian logarit. Nó thường thấy trong các thuật toán sắp xếp (e. g. sáp nhập, timsort, heapsort)

Ví dụ. đối với mỗi giá trị trong dữ liệu1 (O(n)) sử dụng tìm kiếm nhị phân (O(log n)) để tìm kiếm cùng một giá trị trong dữ liệu2

for value in data1:
    result.append(binary_search(data2, value))

Một ví dụ khác, phức tạp hơn, có thể được tìm thấy trong thuật toán Mergesort. Mergesort là một thuật toán sắp xếp dựa trên so sánh, có mục đích chung, hiệu quả, có độ phức tạp về thời gian gần như tuyến tính, hãy xem một ví dụ

________số 8

Hình ảnh sau đây minh họa các bước được thực hiện bởi thuật toán sắp xếp hợp nhất

ví dụ hợp nhất. https. // vi. wikipedia. org/wiki/Hợp nhất_sắp xếp

Lưu ý rằng trong ví dụ này, việc sắp xếp đang được thực hiện tại chỗ

Thời gian bậc hai — O(n²)

Một thuật toán được cho là có độ phức tạp thời gian bậc hai khi nó cần thực hiện một phép toán thời gian tuyến tính cho từng giá trị trong dữ liệu đầu vào, chẳng hạn

for x in data:
    for y in data:
        print(x, y)

Sắp xếp bong bóng là một ví dụ tuyệt vời về độ phức tạp của thời gian bậc hai vì đối với mỗi giá trị, nó cần so sánh với tất cả các giá trị khác trong danh sách, hãy xem một ví dụ

if a > b:
    return True
else:
    return False

0

Thời gian theo cấp số nhân — O(2^n)

Một thuật toán được cho là có độ phức tạp theo cấp số nhân khi tốc độ tăng trưởng tăng gấp đôi với mỗi lần thêm vào tập dữ liệu đầu vào. Loại thời gian phức tạp này thường thấy trong các thuật toán brute-force

Ví dụ như Vicky Lai

Trong mật mã, một cuộc tấn công vũ phu có thể kiểm tra một cách có hệ thống tất cả các yếu tố có thể có của mật khẩu bằng cách lặp qua các tập hợp con. Sử dụng một thuật toán hàm mũ để làm điều này, nó trở nên cực kỳ tốn kém tài nguyên để bẻ khóa một mật khẩu dài so với một mật khẩu ngắn hơn. Đây là một lý do mà mật khẩu dài được coi là an toàn hơn mật khẩu ngắn hơn

Một ví dụ khác về thuật toán thời gian hàm mũ là tính toán đệ quy các số Fibonacci

if a > b:
    return True
else:
    return False

1

Nếu bạn chưa biết hàm đệ quy là gì, hãy nhanh chóng làm rõ nó. một hàm đệ quy có thể được mô tả như một hàm gọi chính nó trong các điều kiện cụ thể. Như bạn có thể nhận thấy, độ phức tạp về thời gian của các hàm đệ quy khó xác định hơn một chút vì nó phụ thuộc vào số lần hàm được gọi và độ phức tạp về thời gian của một lần gọi hàm.

Sẽ hợp lý hơn khi chúng ta nhìn vào cây đệ quy. Cây đệ quy sau được tạo bởi thuật toán Fibonacci sử dụng n = 4

Cây đệ quy của Fibonacci(4). https. //visualgo. ròng/tỷ/đệ quy

Lưu ý rằng nó sẽ tự gọi cho đến khi chạm đến lá. Khi đến các lá, nó sẽ tự trả về giá trị

Bây giờ, hãy xem cây đệ quy phát triển như thế nào khi tăng n lên 6

Cây đệ quy của Fibonacci(6). https. //visualgo. ròng/tỷ/đệ quy

Bạn có thể tìm thấy lời giải thích đầy đủ hơn về độ phức tạp thời gian của thuật toán Fibonacci đệ quy tại đây trên StackOverflow

Giai thừa — O(n. )

Một thuật toán được cho là có độ phức tạp thời gian giai thừa khi nó phát triển theo cách giai thừa dựa trên kích thước của dữ liệu đầu vào, chẳng hạn

if a > b:
    return True
else:
    return False

2

Như bạn có thể thấy, nó phát triển rất nhanh, ngay cả đối với đầu vào có kích thước nhỏ

Một ví dụ tuyệt vời về thuật toán có độ phức tạp thời gian giai thừa là thuật toán Heap, được sử dụng để tạo tất cả các hoán vị có thể có của n đối tượng

Theo Wikipedia

Heap đã tìm ra một phương pháp có hệ thống để chọn ở mỗi bước một cặp phần tử để chuyển đổi, nhằm tạo ra mọi hoán vị có thể có của các phần tử này chính xác một lần

Hãy xem ví dụ

if a > b:
    return True
else:
    return False

3

Kết quả sẽ là

if a > b:
    return True
else:
    return False

4

Lưu ý rằng nó sẽ phát triển theo cách giai thừa, dựa trên kích thước của dữ liệu đầu vào, vì vậy có thể nói thuật toán có độ phức tạp thời gian giai thừa O(n. )

Một ví dụ tuyệt vời khác là Vấn đề người bán hàng du lịch

Ghi chú quan trọng

Điều quan trọng cần lưu ý là khi phân tích độ phức tạp thời gian của một thuật toán với một số hoạt động, chúng ta cần mô tả thuật toán dựa trên độ phức tạp lớn nhất trong số tất cả các hoạt động. Ví dụ

if a > b:
    return True
else:
    return False

5

Ngay cả khi các hoạt động trong 'my_function' không có ý nghĩa gì, chúng ta có thể thấy rằng nó có nhiều độ phức tạp về thời gian. O(1) + O(n) + O(n²). Vì vậy, khi tăng kích thước dữ liệu đầu vào, nút cổ chai của thuật toán này sẽ là phép toán chiếm O(n²). Dựa trên điều này, chúng ta có thể mô tả độ phức tạp thời gian của thuật toán này là O(n²)

Bảng gian lận Big-O

Để làm cho cuộc sống của bạn dễ dàng hơn, tại đây bạn có thể tìm thấy một trang tính có độ phức tạp về thời gian của các thao tác trong các cấu trúc dữ liệu phổ biến nhất

Hoạt động cấu trúc dữ liệu chung. http. //bigocheatsheet. com/

Đây là một trang khác với độ phức tạp về thời gian của các thuật toán sắp xếp phổ biến nhất

Thuật toán sắp xếp mảng. http. //bigocheatsheet. com/Tại sao điều quan trọng là phải biết tất cả những điều này?

Nếu sau khi đọc hết câu chuyện này, bạn vẫn còn nghi ngờ về tầm quan trọng của việc biết độ phức tạp của thời gian và ký hiệu Big-O, hãy làm rõ một số điểm

Ngay cả khi làm việc với các ngôn ngữ hiện đại, như Python, cung cấp các chức năng tích hợp sẵn, chẳng hạn như thuật toán sắp xếp, một ngày nào đó bạn có thể sẽ cần triển khai một thuật toán để thực hiện một số loại thao tác trong một lượng dữ liệu nhất định. Bằng cách nghiên cứu độ phức tạp của thời gian, bạn sẽ hiểu khái niệm quan trọng về hiệu quả và sẽ có thể tìm thấy các nút thắt cổ chai trong mã của mình cần được cải thiện, chủ yếu khi làm việc với các tập dữ liệu khổng lồ

Bên cạnh đó, nếu bạn dự định ứng tuyển vào vị trí kỹ sư phần mềm trong một công ty lớn như Google, Facebook, Twitter và Amazon, bạn sẽ cần chuẩn bị sẵn sàng để trả lời các câu hỏi về độ phức tạp của thời gian bằng cách sử dụng ký hiệu Big-O

Ghi chú cuối cùng

Cảm ơn đã đọc câu chuyện này. Tôi hy vọng bạn đã học thêm một chút về độ phức tạp của thời gian và ký hiệu Big-O. Nếu bạn thích nó, hãy vỗ tay và chia sẻ nó. Nếu bạn có bất kỳ nghi ngờ hoặc gợi ý nào, vui lòng bình luận hoặc gửi email cho tôi. Ngoài ra, vui lòng theo dõi tôi trên Twitter, Linkedin và Github

Làm thế nào chúng ta có thể giảm thời gian phức tạp của mã?

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