Phân tích các thuật toán (phức tạp)

Question

Thuật toán được phân tích như thế nào? Điều gì làm cho quicksort có hiệu suất trường hợp xấu nhất O(n^2) trong khi sắp xếp hợp nhất có hiệu suất trường hợp xấu nhất O(n log(n))?

Answer 1

Đó là chủ đề cho toàn bộ học kỳ. Cuối cùng chúng ta đang nói về giới hạn trên về số lượng hoạt động phải được hoàn thành trước khi thuật toán kết thúc như một hàm của kích thước của đầu vào. Chúng tôi không bao gồm các coeffecients (tức là 10N vs 4N^2) bởi vì đối với N đủ lớn, nó không quan trọng nữa.

Làm thế nào để chứng minh những gì lớn-oh của một thuật toán có thể khá khó khăn. Nó đòi hỏi một bằng chứng chính thức và có rất nhiều kỹ thuật. Thường thì một cách adhoc tốt là chỉ đếm số lượng dữ liệu mà thuật toán tạo ra. Ví dụ, nếu thuật toán của bạn đã lồng nhau cho các vòng lặp, thì đối với mỗi mục N bạn phải vận hành N lần. Đó thường sẽ là O (N^2).

Để hợp nhất sắp xếp, bạn chia nhỏ dữ liệu một nửa và hơn. Điều đó có log2 (n). Và đối với mỗi lần chia, bạn thực hiện truyền dữ liệu, cung cấp cho N log (n).

sắp xếp nhanh hơn một chút phức tạp hơn vì trong trường hợp trung bình, nó cũng là n log (n). Bạn phải tưởng tượng điều gì sẽ xảy ra nếu phân vùng của bạn chia tách dữ liệu sao cho mỗi lần bạn chỉ nhận được một phần tử ở một bên của phân vùng. Sau đó, bạn sẽ cần phải chia dữ liệu n lần thay vì log (n) lần mà làm cho nó N^2. Ưu điểm của quicksort là nó có thể được thực hiện tại chỗ và chúng ta thường tiến gần hơn đến hiệu suất N log (n).

Answer 2

Cả hai quicksort và merge sort chia mảng thành hai, sắp xếp từng phần một cách đệ quy, sau đó kết hợp kết quả. Quicksort chia tách bằng cách chọn phần tử "pivot" và phân vùng mảng thành nhỏ hơn hoặc lớn hơn sau đó là trục xoay. Hợp nhất các phân chia phân loại tùy ý và sau đó kết hợp các kết quả theo thời gian tuyến tính. Trong cả hai trường hợp, một bước duy nhất là O (n) và nếu kích thước mảng giảm một nửa thì điều này sẽ cung cấp cho một số bước lôgarít. Vì vậy, chúng tôi mong đợi O (n log (n)).

Tuy nhiên, trường hợp nhanh nhất có trường hợp xấu nhất khi phân chia luôn không đồng đều, do đó bạn không nhận được một số bước tỷ lệ thuận với logarit của n, nhưng một số bước tỷ lệ thuận với n. Hợp nhất phân chia chính xác thành hai nửa (hoặc càng gần càng tốt) để nó không có vấn đề này.

Answer 3

• loại nhanh có nhiều biến thể tùy thuộc vào lựa chọn trục
• Giả sử chúng tôi luôn chọn mục 1 trong mảng như một trục

Nếu mảng đầu vào được sắp xếp sau đó sắp xếp nhanh sẽ chỉ có một loại lựa chọn sắp xếp! Vì bạn không thực sự phân chia mảng .. bạn chỉ chọn mục đầu tiên trong mỗi chu kỳ

Mặt khác, sắp xếp hợp nhất sẽ luôn phân chia mảng đầu vào theo cách tương tự, bất kể nội dung của nó là gì!

Cũng lưu ý: hiệu suất tốt nhất trong chia và chinh phục khi độ dài phân chia là -gần bằng nhau!

Answer 4

1. Đây là phân tích giới thiệu các tài liệu khóa học thuật toán.

2. Một thao tác được xác định (nghĩa là nhân) và phân tích được thực hiện theo cả không gian hoặc thời gian.

3. Thao tác này được tính theo không gian hoặc thời gian.Các phân tích thông thường được thực hiện dưới dạng Thời gian là biến phụ thuộc khi Kích thước đầu vào.

Ví dụ giả:

foreach $elem in @list 

    op(); 

endfor 

Sẽ có n hoạt động biểu diễn, nơi n là kích thước của @list. Đếm nó cho mình nếu bạn không tin tôi.

Để phân tích quicksort và mergesort yêu cầu một mức độ phong nha của những gì được gọi là tinh tế toán học. Một cách lỏng lẻo, bạn giải quyết một phương trình vi phân rời rạc xuất phát từ mối quan hệ đệ quy.