Big Oh for (n log n)

Question

Tôi hiện đang nghiên cứu các thuật toán cơ bản cho Big Oh. Tôi đã tự hỏi nếu có ai có thể chỉ cho tôi những gì mã cho (n log n) trong Java bằng cách sử dụng Big Oh sẽ được như thế hoặc trực tiếp tôi đến bất kỳ trang SO nơi một tồn tại.

Vì tôi chỉ là người mới bắt đầu, tôi chỉ có thể tưởng tượng mã trước khi viết. Vì vậy, về mặt lý thuyết (ít nhất), nó nên chứa một cho vòng lặp, nơi chúng tôi có một cái gì đó của n lần. Sau đó, đối với log n, chúng ta có thể sử dụng vòng lặp while. Vì vậy, vòng lặp được thực hiện n lần và vòng lặp while được thực thi cơ sở log 2 lần. Ít nhất đó là cách tôi tưởng tượng nó trong đầu tôi, nhưng nhìn thấy mã sẽ làm rõ mọi thứ.

Answer 1

Thuật toán O (n log n) rất phổ biến là hợp nhất sắp xếp. http://en.wikipedia.org/wiki/Merge_sort ví dụ về thuật toán và mã giả. Phần log của thuật toán được thực hiện thông qua việc chia nhỏ vấn đề thành các bài toán con nhỏ hơn, trong đó chiều cao của cây đệ quy là log n.

Rất nhiều phân loại algortihms có thời gian chạy của O (n log n). Tham khảo http://en.wikipedia.org/wiki/Sorting_algorithm để biết thêm ví dụ.

Answer 2

http://en.wikipedia.org/wiki/Heapsort

Ví dụ đơn giản là giống như bạn mô tả - thực hiện n lần một số thao tác nào cần log (n) thời gian. Cây nhị phân cân bằng có chiều cao log (n), vì vậy một số thuật toán cây sẽ có độ phức tạp như vậy.

Answer 3

int n = 100 
for(int i = 0; i < n; i++) //this loop is executed n times, so O(n) 
{ 
    for(int j = n; j > 0; j/=2) //this loop is executed O(log n) times 
    { 

    } 
} 

Giải thích: Vòng lặp ngoài phải rõ ràng. Nó được thực hiện n lần. Bây giờ đến vòng lặp bên trong. Trong vòng lặp bên trong, bạn chỉ cần n và luôn chia nó theo 2. vì vậy bạn tự hỏi mình: Tôi có thể phân chia bao nhiêu lần n bởi 2.

Nó chỉ ra rằng đây là trong O (log n). (trên thực tế, cơ sở của nhật ký là 2, nhưng trong ký hiệu Big-Oh chúng tôi rời khỏi cơ sở vì nó sẽ chỉ thêm một số yếu tố vào nhật ký của chúng tôi mà chúng tôi không quan tâm).

Vì vậy, bạn đang thực hiện một vòng lặp n lần và trong vòng lặp đó bạn đang thực hiện một vòng lặp khác log(n) lần để bạn có O(n) * O(log n) = O(n log n).

Answer 4

Thuật toán với độ phức tạp thời gian O(.) liên quan đến log n thường liên quan đến một số hình thức phân chia và chinh phục.

Ví dụ: trong MergeSort danh sách bị giảm đi một nửa, mỗi phần được sắp xếp hợp nhất riêng lẻ và sau đó hai nửa được hợp nhất với nhau. Mỗi danh sách được giảm một nửa.

Bất cứ khi nào bạn làm việc giảm một nửa hoặc giảm kích thước theo một số yếu tố cố định, bạn thường sẽ kết thúc với thành phần log n của O(.).

Về mặt mã, hãy xem thuật toán cho MergeSort. Tính năng quan trọng, của việc triển khai điển hình, là nó đệ quy (lưu ý rằng TopDownSplitMerge gọi chính nó hai lần trong mã được đưa ra trên Wikipedia).

Tất cả các thuật toán sắp xếp tiêu chuẩn tốt có độ phức tạp thời gian là O(n log n) và không thể làm tốt hơn trong trường hợp xấu nhất, xem Comparison Sort.

Để xem mã này trông như thế nào trong mã Java, chỉ cần search! Here's one example.