Làm thế nào một thuật toán có thể có hai trường hợp phức tạp tồi tệ nhất?

Question

Bài tập 1 của chương trình Hướng dẫn thiết kế Thuật toán của Steven Skiena có câu hỏi này:

Cho P là một vấn đề. Độ phức tạp thời gian xấu nhất của P là O (n^2). Độ phức tạp thời gian xấu nhất của P cũng là Ω (n log n). Hãy để A là một thuật toán giải quyết P. Tập hợp con nào trong các câu sau đây là phù hợp với thông tin này về độ phức tạp của P?

• A có độ phức tạp thời gian xấu nhất O (n^2).
• A có độ phức tạp thời gian xấu nhất O (n^3/2).
• A có độ phức tạp thời gian xấu nhất O (n).
• A có độ phức tạp thời gian xấu nhất ⍬ (n^2).
• A có độ phức tạp thời gian xấu nhất ⍬ (n^3).

Thuật toán có thể có hai sự phức tạp về thời gian xấu nhất? Tác giả đang cố gắng nói rằng đối với một số giá trị của n (ví dụ: 300) giới hạn trên cho thuật toán được viết để giải quyết P là thứ tự của O (n^2) trong khi giá trị khác là n (ví dụ: 3000) cùng một trường hợp xấu nhất của thuật toán là Ω (n log n)?

Answer 1

Câu trả lời cho câu hỏi cụ thể của bạn

là tác giả cố gắng để nói rằng đối với một số giá trị của n (nói ví dụ 300) trên ràng buộc đối với thuật toán bằng văn bản để giải quyết P là thứ tự của O (n^2) trong khi cho một giá trị khác của n (ví dụ: 3000) cùng một trường hợp thuật toán xấu nhất là Ω (n log n)?

là no. Đó không phải là cách các hàm phức tạp hoạt động. :) Chúng ta không nói về các lớp phức tạp khác nhau cho các giá trị khác nhau của n. Sự phức tạp đề cập đến toàn bộ thuật toán, không phải thuật toán ở các kích thước cụ thể. Thuật toán có hàm phức tạp thời gian đơn T (n), tính toán số bước cần thiết để thực hiện tính toán cho kích thước đầu vào của n.

Trong vấn đề này, bạn có hai mẩu thông tin:

• Trường hợp phức tạp nhất là O (n^2)

• Trường hợp phức tạp nhất là Ω (n log n)

Tất cả điều này có nghĩa là chúng ta có thể chọn các hằng số c1, c2, N1, N2 và, như vậy, đối với chức năng T thuật toán của chúng tôi (n), chúng tôi có

0.123.

• T (n) ≤ c1 * n^2 cho tất cả n ≥ N1

• T (n) ≥ c2 * n log n với mọi n ≥ N2

Trong khác các từ, T (n) của chúng ta được "giới hạn tiệm cận dưới đây" bởi một số thời gian liên tục n log n và "asymptotically bounded above" bởi một số lần liên tục n^2. Nó có thể tự nó là bất cứ thứ gì "giữa" một hàm n n kiểu n và một hàm kiểu n^2. Nó thậm chí có thể là n log n (vì nó bị giới hạn ở trên bởi n^2) hoặc nó có thể là n^2 (vì nó bị chặn dưới đây bởi n log n. Nó có thể là một cái gì đó ở giữa, như n (log n) (log n)

Không quá nhiều khi thuật toán có "nhiều trường hợp phức tạp tồi tệ nhất" theo nghĩa nó có các hành vi khác nhau. Bạn thấy gì là giới hạn trên và giới hạn thấp hơn! . khác nhau

Bây giờ nó là thể rằng bạn có một số chức năng "kỳ lạ" như thế này:

def p(n): 
    if n is even: 
     print n log n stars 
    else: 
     print n*2 stars 

thuật toán điên này không h ave các giới hạn được chỉ định trong bài toán từ cuốn sách Skiena. Và nó không có độ phức tạp Θ. Đó có thể là những gì bạn đang nghĩ đến, nhưng lưu ý rằng không cần thiết phải có một hàm phức tạp để có thể lạ lùng này để chúng ta có thể nói rằng giới hạn trên và dưới khác nhau. Điều cần ghi nhớ là giới hạn trên và dưới không phải là chặt chẽ trừ khi được tuyên bố rõ ràng như vậy.