Làm thế nào để tính toán thứ tự (lớn O) cho các thuật toán phức tạp hơn (ví dụ như quicksort)

Question

Tôi biết có khá một loạt các câu hỏi về ký hiệu O lớn, tôi đã kiểm tra:

• Plain english explanation of Big O
• Big O, how do you calculate/approximate it?
• Big O Notation Homework--Code Fragment Algorithm Analysis?

để đặt tên một vài.

tôi biết bằng cách "trực giác" làm thế nào để tính toán nó cho n, n^2, n! và như vậy, tuy nhiên tôi hoàn toàn bị mất trên làm thế nào để tính toán nó cho các thuật toán mà log n, n log n, n log log n và như vậy.

Ý của tôi là, tôi biết rằng Sắp xếp nhanh là n log n (trung bình) .. nhưng, lý do tại sao? Điều tương tự cho hợp nhất/lược, v.v.

Ai đó có thể giải thích cho tôi theo cách không quá toán-y như thế nào để bạn tính toán điều này?

Lý do chính là tôi sắp có một cuộc phỏng vấn lớn và tôi chắc chắn họ sẽ yêu cầu loại nội dung này. Tôi đã nghiên cứu vài ngày nay và mọi người dường như có giải thích về lý do tại sao loại bong bóng là n^2 hoặc lời giải thích không thể đọc được (đối với tôi) trên Wikipedia

Answer 1

Lôgarit là hoạt động nghịch đảo của lũy thừa. Ví dụ về lũy thừa là khi bạn tăng gấp đôi số lượng mục tại mỗi bước. Do đó, thuật toán logarit thường giảm một nửa số lượng mục ở mỗi bước. Ví dụ: tìm kiếm nhị phân thuộc danh mục này.

Nhiều thuật toán yêu cầu một số lượng lớn các bước lớn, nhưng mỗi bước lớn yêu cầu đơn vị công việc O (n). Mergesort thuộc danh mục này.

Thông thường bạn có thể xác định các loại vấn đề này bằng cách trực quan hóa chúng dưới dạng cây nhị phân cân bằng. Ví dụ: đây là loại hợp nhất:

6 2 0 4 1 3  7 5 
    2 6  0 4  1 3  5 7 
    0 2 4 6   1 3 5 7 
     0 1 2 3 4 5 6 7 

Ở trên cùng là đầu vào, làm lá của cây. Thuật toán tạo ra một nút mới bằng cách sắp xếp hai nút ở trên nó. Chúng ta biết chiều cao của cây nhị phân cân bằng là O (log n) vì vậy có các bước lớn O (log n). Tuy nhiên, việc tạo mỗi hàng mới sẽ thực hiện công việc O (n). O (log n) các bước lớn của O (n) làm việc mỗi phương tiện rằng mergesort là O (n log n) tổng thể.

Nói chung, các thuật toán O (log n) trông giống như hàm bên dưới. Họ có thể loại bỏ một nửa dữ liệu ở mỗi bước.

def function(data, n): 
    if n <= constant: 
     return do_simple_case(data, n) 
    if some_condition(): 
     function(data[:n/2], n/2) # Recurse on first half of data 
    else: 
     function(data[n/2:], n - n/2) # Recurse on second half of data 

Khi thuật toán O (n log n) trông giống như hàm bên dưới. Họ cũng chia dữ liệu thành một nửa, nhưng họ cần xem xét cả hai nửa.

def function(data, n): 
    if n <= constant: 
     return do_simple_case(data, n) 
    part1 = function(data[n/2:], n/2)  # Recurse on first half of data 
    part2 = function(data[:n/2], n - n/2) # Recurse on second half of data 
    return combine(part1, part2) 

Nơi do_simple_case() mất O (1) thời gian và kết hợp() không quá O (n) lần.

Thuật toán không cần chia nhỏ dữ liệu một nửa. Họ có thể chia nó thành một phần ba và hai phần ba, và điều đó sẽ ổn thôi. Đối với hiệu suất trung bình, chia tách nó thành một nửa trung bình là đủ (như QuickSort). Miễn là đệ quy được thực hiện trên miếng (n/cái gì đó) và (n - n/cái gì đó), nó là okay. Nếu nó phá vỡ nó thành (k) và (n-k) thì chiều cao của cây sẽ là O (n) và không phải O (log n).

Answer 2

Bạn thường có thể yêu cầu nhật ký n cho các thuật toán trong đó một nửa không gian/thời gian mỗi khi nó chạy. Một ví dụ tốt về điều này là bất kỳ thuật toán nhị phân nào (ví dụ: tìm kiếm nhị phân). Bạn chọn một trong hai trái hoặc phải, sau đó trục không gian bạn đang tìm kiếm một nửa. Các mô hình liên tục làm một nửa là đăng nhập n.

Answer 3

Khi áp dụng thuật toán phân chia và chinh phục nơi bạn phân tách vấn đề thành các vấn đề phụ cho đến khi nó đơn giản đến mức không phân biệt, kích thước của từng vấn đề phụ là n/2 hoặc thereabout. Đây thường là nguồn gốc của các log(n) mà cây trồng lên trong lớn-O phức tạp: O(log(n)) là số lượng các cuộc gọi đệ quy cần thiết khi phân vùng diễn ra tốt đẹp.

Answer 4

Kiểm tra các "danh bạ điện thoại" dụ đưa ra ở đây: What is a plain English explanation of "Big O" notation?

Hãy nhớ rằng Big-O là tất cả về quy mô : bao nhiêu hoạt động nhiều thuật toán này sẽ đòi hỏi như tập dữ liệu phát triển?

O (log n) thường có nghĩa là bạn có thể cắt các bộ dữ liệu trong nửa với mỗi lần lặp (ví dụ nhị phân tìm kiếm)

O (n log n) có nghĩa là bạn đang thực hiện một O (log n) hoạt động cho mỗi mục trong tập dữ liệu của bạn

Tôi chắc chắn 'O (n log log n)' không có ý nghĩa gì cả. Hoặc nếu có, nó đơn giản hóa xuống O (n log n).

Answer 5

Đối với một số thuật toán, bị ràng buộc chặt chẽ trong thời gian chạy qua trực giác là không thể (tôi không nghĩ rằng mình sẽ có thể intuit thời gian chạy O(n log log n) chẳng hạn) bao giờ mong đợi bạn).Nếu bạn có thể nhận được bàn tay của bạn trên CLRS Introduction to Algorithms text, bạn sẽ tìm thấy một điều trị khá kỹ lưỡng của ký hiệu tiệm cận mà là một cách thích hợp nghiêm ngặt mà không hoàn toàn mờ đục.

Nếu thuật toán đệ quy, một cách đơn giản để lấy được giới hạn là viết ra sự lặp lại và sau đó đặt ra để giải quyết nó, hoặc lặp lại hoặc sử dụng Master Theorem hoặc một số cách khác. Ví dụ, nếu bạn không tìm kiếm siêu nghiêm ngặt về nó, cách dễ nhất để có được thời gian chạy của QuickSort là thông qua Định lý chính - QuickSort đòi hỏi phân vùng mảng thành hai mảng con tương đối bằng nhau (cần khá trực quan để thấy rằng đây là O(n)), và sau đó gọi QuickSort đệ quy trên hai mạng con đó. Sau đó, nếu chúng tôi cho phép T(n) biểu thị thời gian chạy, chúng tôi có T(n) = 2T(n/2) + O(n), theo Phương thức chính là O(n log n).

Answer 6

Tôi sẽ cố gắng phân tích trực quan lý do tại sao Mergesort là n log n và nếu bạn có thể cho tôi ví dụ về thuật toán n log log n, tôi cũng có thể làm việc thông qua nó.

Mergesort là một ví dụ sắp xếp hoạt động thông qua tách danh sách các phần tử liên tục cho đến khi chỉ có các phần tử tồn tại và sau đó hợp nhất các danh sách này lại với nhau. Hoạt động chính trong mỗi lần hợp nhất này là so sánh và mỗi lần hợp nhất yêu cầu nhiều nhất so sánh n trong đó n là độ dài của hai danh sách được kết hợp. Từ đó bạn có thể lấy được sự tái diễn và dễ dàng giải quyết nó, nhưng chúng ta sẽ tránh phương pháp đó. Thay vào đó hãy xem xét cách Mergesort sẽ hành xử, chúng ta sẽ lấy một danh sách và chia nhỏ nó, sau đó lấy nửa đó và chia nó một lần nữa, cho đến khi chúng ta có n phân đoạn chiều dài 1. Tôi hy vọng rằng nó dễ dàng nhìn thấy rằng đệ quy này sẽ chỉ đi sâu vào log (n) cho đến khi chúng ta chia danh sách thành các phân vùng n của chúng ta.

Bây giờ chúng ta có mỗi phân vùng n sẽ cần được hợp nhất, sau đó một khi chúng được hợp nhất cấp tiếp theo sẽ cần phải được hợp nhất, cho đến khi chúng ta có danh sách độ dài n lần nữa. Tham khảo đồ họa của wikipedia để biết ví dụ đơn giản về quy trình này http://en.wikipedia.org/wiki/File:Merge_sort_algorithm_diagram.svg.

Bây giờ hãy xem xét lượng thời gian mà quá trình này sẽ thực hiện, chúng ta sẽ có các cấp độ (n) và ở mỗi cấp, chúng ta sẽ phải hợp nhất tất cả các danh sách. Khi nó quay ra mỗi cấp độ sẽ mất thời gian để hợp nhất, bởi vì chúng tôi sẽ hợp nhất tổng số phần tử n mỗi lần. Sau đó, bạn có thể dễ dàng thấy rằng sẽ mất thời gian n log (n) để sắp xếp một mảng với mergesort nếu bạn thực hiện phép so sánh là hoạt động quan trọng nhất.

Nếu có gì không rõ ràng hoặc tôi bỏ qua ở đâu đó, vui lòng cho tôi biết và tôi có thể cố gắng tiết lộ chi tiết hơn.

Chỉnh sửa giải thích thứ hai:

Hãy để tôi nghĩ rằng nếu tôi có thể giải thích điều này tốt hơn.

Sự cố được chia thành một loạt các danh sách nhỏ hơn và sau đó các danh sách nhỏ hơn được sắp xếp và hợp nhất cho đến khi bạn quay trở lại danh sách ban đầu đã được sắp xếp.

Khi bạn chia nhỏ các vấn đề bạn có nhiều cấp độ khác nhau trước tiên, bạn sẽ có hai danh sách kích thước: n/2, n/2 thì ở cấp tiếp theo bạn sẽ có bốn danh sách kích thước: n/4, n/4, n/4, n/4 ở cấp độ tiếp theo bạn sẽ có n/8, n/8, n/8, n/8, n/8, n/8, n/8, n/8 điều này tiếp tục cho đến khi n/2^k bằng 1 (mỗi phân khu là chiều dài chia cho một lũy thừa của 2, không phải tất cả độ dài sẽ chia hết cho bốn vì vậy nó sẽ không được khá đẹp). Điều này được lặp lại chia cho hai và có thể tiếp tục nhiều nhất log_2 (n) lần, bởi vì 2^(log_2 (n)) = n, vì vậy bất kỳ phân chia nào thêm 2 sẽ mang lại một danh sách có kích thước bằng không.

Bây giờ điều quan trọng cần lưu ý là ở mọi cấp độ chúng ta có n phần tử sao cho mỗi cấp độ hợp nhất sẽ mất thời gian, bởi vì hợp nhất là một phép toán tuyến tính. Nếu có mức log (n) của đệ quy thì chúng ta sẽ thực hiện lần log hoạt động tuyến tính (n) lần này, do đó thời gian chạy của chúng ta sẽ là n log (n).

Xin lỗi nếu điều đó không hữu ích.