Nó sẽ không đủ để cung cấp cho một đầu vào đặc biệt và thấy chạy thời gian tối thiểu là f (n)?
Vâng, giả sử bạn đang nói về trường hợp xấu nhất phức tạp.
Nếu bạn đang nói về sự phức tạp của trường hợp xấu nhất - và bạn đã chứng tỏ nó đang chạy trong O(f(n)), nếu bạn tìm thấy đầu vào "tồi tệ" hơn C*f(n)) đối với một số hằng số C - bạn đã chứng minh hiệu quả thuật toán (trong trường hợp xấu nhất) trong Ω(f(n)) và kể từ O(f(n)) [intersection] Ω(f(n)) = Theta(f(n)), điều đó có nghĩa là thuật toán của bạn đang chạy trong Theta(f(n)) trong phân tích trường hợp xấu nhất.
Note rằng nó thực sự phải là một "gia đình" của ví dụ, vì nếu tôi tuyên bố "có, nhưng điều này là chính xác chỉ cho n giá trị nhỏ, và không cho n>N (đối với một số N), bạn có thể chỉ cho tôi rằng đây gia đình của ví dụ này cũng bao gồm các trường hợp n>N, và vẫn còn có giá trị.
Tương tự, nếu bạn tỏ ra một thuật toán có hiệu suất trường hợp tốt nhất của Ω(f(n)), và bạn tìm thấy một số đầu vào mà chạy "tốt hơn" (nhanh hơn) so với C*f(n)) đối với một số hằng số C, bạn đã chứng minh hiệu quả thuật toán là Theta(f(n)) trong phân tích trường hợp tốt nhất.
Thủ thuật này KHÔNG làm việc cho phân tích trường hợp trung bình - nơi bạn nên tính toán thời gian chạy của thời gian chạy, và một ví dụ số ít không hữu ích.
Tôi đã đọc rằng một khả năng để chứng minh độ kín là "giảm bớt số phân loại cho nó". Tôi không biết những gì có nghĩa là rằng
này được thực hiện để chứng minh yêu cầu bồi thường mạnh hơn rất nhiều, đó không có thuật toán (ở tất cả) có thể giải quyết một số vấn đề ở thời điểm mong muốn.
Cách sử dụng phổ biến của nó là giả sử có một số thuật toán hộp đen A chạy trong khoảng thời gian o(g(n)) và sau đó sử dụng A để tạo thuật toán sắp xếp chạy trong thời gian o(nlogn). Tuy nhiên, kể từ khi phân loại là Ω(nlogn) vấn đề, chúng tôi có mâu thuẫn và chúng tôi có thể kết luận các giả định về A là sai và không thể chạy trong thời gian mong muốn.
Điều này giúp chúng tôi chứng minh một tuyên bố mạnh mẽ hơn: Không chỉ thuật toán của chúng tôi có giới hạn dưới này, nhưng TẤT CẢ các thuật toán giải quyết vấn đề cụ thể có giới hạn dưới này.
Vì vậy, tôi cần chứng minh rằng vấn đề, thuật toán của tôi giải quyết, tương đương với vấn đề phân loại dữ liệu, đúng không? – 0xbadf00d
@ 0xbadf00d Không chính xác, bạn có thể chỉ ra rằng bạn có thể giải quyết việc sắp xếp với nó trong thời gian o (nlogn). – amit