Thời gian tối thiểu để thực hiện thuật toán với dữ liệu đầu vào kích thước n được kí hiệu là gì

bài viết này cần trích dẫn bổ sung cho xác minh. Xin vui lòng giúp đỡ cải thiện bài viết này bởi thêm trích dẫn vào các nguồn đáng tin cậy. Vật liệu không có nguồn gốc có thể bị thách thức và loại bỏ. Tìm nguồn:"Trường hợp tốt nhất, xấu nhất và trung bình"Tin tức· Báo· sách· học giả· JSTOR [] [Tìm hiểu cách thức và thời điểm xóa thông báo mẫu này]

Trong khoa học máy tính, tốt, tệ nhất, và trường hợp trung bình của một thuật toán diễn đạt những gì nguồn sử dụng là ít nhất, nhất và Trung bình, tương ứng. Thông thường, tài nguyên đang được xem xét là thời gian chạy, tức là thời gian phức tạp, nhưng cũng có thể là bộ nhớ hoặc tài nguyên khác. Trường hợp tốt nhất là hàm thực hiện số bước tối thiểu trên dữ liệu đầu vào của n phần tử. Trường hợp xấu nhất là hàm thực hiện số bước tối đa trên dữ liệu đầu vào có kích thước n. là hàm thực hiện một số bước trung bình trên dữ liệu đầu vào của n phần tử.

Trong tính toán thời gian thực, các thời gian thực hiện trường hợp xấu nhất thường được quan tâm đặc biệt vì điều quan trọng là phải biết có thể cần bao nhiêu thời gian trong trường hợp xấu nhất để đảm bảo rằng thuật toán sẽ luôn hoàn thành đúng thời gian.

Hiệu suất trung bình và hiệu suất trong trường hợp xấu nhất được sử dụng nhiều nhất trong phân tích thuật toán. Ít được tìm thấy hơn là hiệu suất trường hợp tốt nhất, nhưng nó có các công dụng: ví dụ, khi các trường hợp tốt nhất của các nhiệm vụ riêng lẻ được biết đến, chúng có thể được sử dụng để cải thiện độ chính xác của phân tích trường hợp xấu nhất tổng thể. Nhà khoa học máy tính sử dụng phân tích xác suất kỹ thuật, đặc biệt là gia trị được ki vọng, để xác định thời gian chạy dự kiến.

Các thuật ngữ được sử dụng trong các ngữ cảnh khác; ví dụ: kết quả xấu nhất và trường hợp tốt nhất của một trận dịch, nhiệt độ trong trường hợp xấu nhất mà một phần tử mạch điện tử tiếp xúc, v.v ... Khi các thành phần được chỉ định lòng khoan dung được sử dụng, các thiết bị phải được thiết kế để hoạt động tốt với sự kết hợp của dung sai và điều kiện bên ngoài trong trường hợp xấu nhất.

Hiệu suất trường hợp tốt nhất cho thuật toán

Thời hạn hiệu suất trường hợp tốt nhất được sử dụng trong khoa học máy tính để mô tả hành vi của thuật toán trong điều kiện tối ưu. Ví dụ: trường hợp tốt nhất cho tìm kiếm tuyến tính đơn giản trên danh sách xảy ra khi phần tử mong muốn là phần tử đầu tiên của danh sách.

Việc phát triển và lựa chọn các thuật toán hiếm khi dựa trên hiệu suất trong trường hợp tốt nhất: hầu hết các doanh nghiệp học thuật và thương mại quan tâm nhiều hơn đến việc cải thiện Độ phức tạp của trường hợp trung bình và hiệu suất trong trường hợp xấu nhất. Các thuật toán cũng có thể được sửa đổi nhỏ để có thời gian chạy trong trường hợp tốt nhất bằng các giải pháp mã hóa cứng cho một nhóm đầu vào hữu hạn, làm cho phép đo gần như vô nghĩa.[1]

Hiệu suất trường hợp xấu nhất so với trường hợp trung bình

Phần này không làm trích dẫn bất kì nguồn. Xin vui lòng giúp đỡ cải thiện phần này bởi thêm trích dẫn vào các nguồn đáng tin cậy. Vật liệu không có nguồn gốc có thể bị thách thức và loại bỏ. [] [Tìm hiểu cách thức và thời điểm xóa thông báo mẫu này]

Phân tích hiệu suất trường hợp xấu nhất và phân tích hiệu suất trường hợp trung bình có một số điểm tương đồng, nhưng trong thực tế thường yêu cầu các công cụ và cách tiếp cận khác nhau.

Xác định những gì đầu vào điển hình rất khó và thường thì đầu vào trung bình có các thuộc tính khiến việc mô tả về mặt toán học trở nên khó khăn [ví dụ: hãy xem xét các thuật toán được thiết kế để hoạt động dây của văn bản]. Tương tự, ngay cả khi có thể mô tả hợp lý về một "trường hợp trung bình" cụ thể [có thể chỉ áp dụng cho một số trường hợp sử dụng thuật toán], chúng có xu hướng dẫn đến việc phân tích các phương trình khó khăn hơn.[2]

Phân tích trường hợp xấu nhất đưa ra một an toàn phân tích [trường hợp xấu nhất không bao giờ được đánh giá thấp], nhưng một trong đó có thể quá bi quan, vì có thể không có đầu vào [thực tế] sẽ thực hiện nhiều bước này.

Trong một số tình huống, có thể cần sử dụng phân tích bi quan để đảm bảo an toàn. Tuy nhiên, thông thường, một phân tích bi quan có thể quá bi quan, vì vậy một phân tích gần với giá trị thực nhưng có thể lạc quan [có lẽ với một số xác suất thất bại đã biết là thấp] có thể là một cách tiếp cận thực tế hơn nhiều. Một cách tiếp cận hiện đại trong lý thuyết hàn lâm để thu hẹp khoảng cách giữa phân tích trường hợp xấu nhất và trường hợp trung bình được gọi là phân tích mịn.

Khi phân tích các thuật toán thường mất một thời gian nhỏ để hoàn thành, nhưng định kỳ đòi hỏi thời gian lớn hơn nhiều, phân tích khấu hao có thể được sử dụng để xác định thời gian chạy trong trường hợp xấu nhất trong một chuỗi [có thể là vô hạn] hoạt động. Điều này trường hợp xấu nhất được khấu hao chi phí có thể gần hơn nhiều so với chi phí trường hợp trung bình, trong khi vẫn cung cấp giới hạn trên được đảm bảo về thời gian chạy.

Phân tích trường hợp xấu nhất liên quan đến trường hợp xấu nhất phức tạp.[3]

Hệ quả thực tế

Nhiều thuật toán có hiệu suất trong trường hợp xấu nhất có hiệu suất trong trường hợp trung bình tốt. Đối với các vấn đề chúng tôi muốn giải quyết, đây là một điều tốt: chúng tôi có thể hy vọng rằng các trường hợp cụ thể mà chúng tôi quan tâm là trung bình. Đối với mật mã, điều này rất tệ: chúng tôi muốn các trường hợp điển hình của một vấn đề mật mã trở nên khó khăn. Tại đây các phương pháp như khả năng tự giảm ngẫu nhiên có thể được sử dụng cho một số bài toán cụ thể để chỉ ra rằng trường hợp xấu nhất không khó hơn trường hợp trung bình, hoặc tương đương, trường hợp trung bình không dễ hơn trường hợp xấu nhất.

Mặt khác, một số cấu trúc dữ liệu như bảng băm có các hành vi trong trường hợp xấu nhất rất kém, nhưng một bảng băm được viết tốt với kích thước đủ lớn sẽ không bao giờ đưa ra trường hợp xấu nhất về mặt thống kê; số lượng hoạt động trung bình được thực hiện tuân theo một đường cong giảm dần hàm mũ và do đó, thời gian chạy của một hoạt động được giới hạn theo thống kê.

Ví dụ

Các thuật toán sắp xếp

Thuật toánCấu trúc dữ liệuThời gian phức tạp: Tốt nhấtĐộ phức tạp về thời gian: Trung bìnhThời gian phức tạp: Tệ nhấtKhông gian phức tạp: Tồi tệ nhất

Sắp xếp nhanh chóng	Mảng	O [n log [n]]	O [n log [n]]	O [n2]	O [n]
Hợp nhất sắp xếp	Mảng	O [n log [n]]	O [n log [n]]	O [n log [n]]	O [n]
Sắp xếp đống	Mảng	O [n log [n]]	O [n log [n]]	O [n log [n]]	O [1]
Sắp xếp mượt mà	Mảng	O [n]	O [n log [n]]	O [n log [n]]	O [1]
Sắp xếp bong bóng	Mảng	O [n]	O [n2]	O [n2]	O [1]
Sắp xếp chèn	Mảng	O [n]	O [n2]	O [n2]	O [1]
Sắp xếp lựa chọn	Mảng	O [n2]	O [n2]	O [n2]	O [1]
Sắp xếp Bogo	Mảng	O [n]	O [n n!]	O []	O [1]

• Sắp xếp chèn áp dụng cho danh sách n , giả định là tất cả các phần tử khác nhau và ban đầu theo thứ tự ngẫu nhiên Trung bình, một nửa phần tử trong danh sách A1 ... Aj ít hơn phần tửAj+1, và một nửa là lớn hơn. Do đó, thuật toán so sánh [j + 1] phần tử thứ sẽ được chèn vào trung bình với một nửa danh sách con đã được sắp xếp, vì vậy tj = j/ 2. Tính toán thời gian chạy trường hợp trung bình thu được sẽ tạo ra một hàm bậc hai của kích thước đầu vào, giống như thời gian chạy trường hợp xấu nhất.
• Sắp xếp nhanh chóng áp dụng cho danh sách n , một lần nữa được giả định là tất cả các phần tử khác nhau và ban đầu theo thứ tự ngẫu nhiên. Phổ biến này thuật toán sắp xếp có hiệu suất theo trường hợp trung bình là O [n log [n]], góp phần làm cho nó trở thành một thuật toán rất nhanh trong thực tế. Nhưng với đầu vào trường hợp xấu nhất, hiệu suất của nó giảm xuống còn O [n2]. Ngoài ra, khi được triển khai với chính sách "đầu tiên ngắn nhất", độ phức tạp không gian trong trường hợp xấu nhất bị giới hạn bởi O [log [n]].
• Heapsort có O [n] thời gian khi tất cả các phần tử đều giống nhau. Heapify mất O [n] thời gian và sau đó xóa các phần tử khỏi đống là O [1] thời gian cho mỗi phần tử trong số n phần tử. Thời gian chạy tăng dần đến O [nlog [n]] nếu tất cả các phần tử phải khác biệt.
• Bogosort có O [n] thời gian khi các phần tử được sắp xếp trong lần lặp đầu tiên. Trong mỗi lần lặp, tất cả các phần tử được kiểm tra nếu theo thứ tự. Có n! các hoán vị có thể có; với bộ tạo số ngẫu nhiên cân bằng, hầu hết mỗi hoán vị của mảng được tạo ra bằng n! các lần lặp lại. Máy tính có bộ nhớ hạn chế, vì vậy các số được tạo ra theo chu kỳ; có thể không đạt được mỗi hoán vị. Trong trường hợp xấu nhất, điều này dẫn đến thời gian O [], một vòng lặp vô hạn.

Cấu trúc dữ liệu

Cấu trúc dữ liệuThời gian phức tạpKhông gian phức tạpTrung bình: Lập chỉ mụcTrung bình: Tìm kiếmTrung bình: ChènTrung bình: XóaTệ nhất: Lập chỉ mụcTệ nhất: Tìm kiếmTồi tệ nhất: ChènTồi tệ nhất: XóaTệ nhất

Căn bản mảng	O [1]	O [n]			O [1]	O [n]			O [n]
Mảng động	O [1]	O [n]	O [n]		O [1]	O [n]	O [n]		O [n]
Danh sách liên kết Singly	O [n]	O [n]	O [1]	O [1]	O [n]	O [n]	O [1]	O [1]	O [n]
Danh sách liên kết kép	O [n]	O [n]	O [1]	O [1]	O [n]	O [n]	O [1]	O [1]	O [n]
Bảng băm		O [1]	O [1]	O [1]		O [n]	O [n]	O [n]	O [n]
Cây tìm kiếm nhị phân		O [log [n]]	O [log [n]]	O [log [n]]		O [n]	O [n]	O [n]	O [n]
Cây B		O [log [n]]	O [log [n]]	O [log [n]]		O [log [n]]	O [log [n]]	O [log [n]]	O [n]
Cây đỏ đen		O [log [n]]	O [log [n]]	O [log [n]]		O [log [n]]	O [log [n]]	O [log [n]]	O [n]
Cây AVL		O [log [n]]	O [log [n]]	O [log [n]]		O [log [n]]	O [log [n]]	O [log [n]]	O [n]

• Tìm kiếm tuyến tính trong danh sách n các yếu tố. Trong trường hợp xấu nhất tuyệt đối, tìm kiếm phải truy cập mọi phần tử một lần. Điều này xảy ra khi giá trị đang được tìm kiếm là phần tử cuối cùng trong danh sách hoặc không có trong danh sách. Tuy nhiên, trung bình, giả sử giá trị được tìm kiếm nằm trong danh sách và mỗi phần tử danh sách đều có khả năng là giá trị được tìm kiếm, thì tìm kiếm chỉ truy cập n/ 2 phần tử.

Xem thêm

• Thuật toán sắp xếp - một khu vực có rất nhiều phân tích hiệu suất của các thuật toán khác nhau.
• Cấu trúc dữ liệu tìm kiếm - bất kỳ cấu trúc dữ liệu nào cho phép truy xuất hiệu quả các mục cụ thể
• Phân tích mạch trường hợp xấu nhất
• Phân tích mượt mà
• Phần tử hữu hạn khoảng cách
• Ký hiệu Big O

Người giới thiệu

Video liên quan