Bị mắc kẹt với ký hiệu O

Question

Tôi đang so sánh hai thuật toán, của Prim và Kruskal.

Tôi hiểu các khái niệm cơ bản của thời gian và phức tạp khi hai tác phẩm hay nhất (thưa thớt/đồ thị dày đặc)

Tôi thấy điều này trên Internet, nhưng tôi đấu tranh để chuyển đổi nó sang tiếng Anh.

dense graph: Prim = O(N2) 
       Kruskal = O(N2*log(N)) 

sparse graph: Prim = O(N2) 
       Kruskal = O(N log(N)) 

Đó là một chút dài, nhưng bất cứ ai có thể giải thích những gì đang xảy ra ở đây?

Answer 1

Prim là O (N^2), trong đó N là số đỉnh.

Kruskal là O (E log E), trong đó E là số cạnh. "E log E" xuất phát từ một thuật toán tốt phân loại các cạnh. Sau đó, bạn có thể xử lý nó trong thời gian E tuyến tính.

Trong biểu đồ dày đặc, E ~ N^2. Vì vậy, Kruskal sẽ là O (N^2 log N^2), mà chỉ đơn giản là O (N^2 log N).

Answer 2

OK, ở đây. O (N2) (2 = bình phương) có nghĩa là tốc độ của thuật toán cho N lớn thay đổi theo hình vuông của N - vì vậy gấp đôi kích thước của đồ thị sẽ dẫn đến gấp bốn lần thời gian tính toán.

Các hàng Kruskal được đơn giản hóa và giả sử rằng E = c * N2. c ở đây có lẽ là một hằng số, mà chúng ta có thể giả định là nhỏ hơn đáng kể so với N khi N lớn. Bạn cần phải biết các định luật sau của logarit: log(ab) = log a + log b và log(a^n) = n * log a. Hai kết hợp này với thực tế là nhật ký c < < Nhật ký N (ít hơn nhiều và có thể bỏ qua) nên cho phép bạn hiểu các đơn giản hóa ở đó.

Bây giờ, đối với các biểu thức ban đầu và nơi chúng được bắt nguồn từ, bạn cần phải kiểm tra trang mà bạn nhận được từ đó. Nhưng tôi giả định rằng nếu bạn nhìn vào Prim và Kruskal thì bạn sẽ có thể hiểu được nguồn gốc, hoặc ít nhất là nếu bạn không thể giải thích nó cho bạn thì thực sự sẽ không giúp bạn về lâu dài ...

Answer 3

Hai thuật toán có định nghĩa O lớn cho các đầu vào khác nhau (nút và cạnh). Vì vậy, họ đang chuyển đổi một để khác để so sánh chúng.

N là các nút số trong biểu đồ E là số cạnh.

cho một đồ thị dày đặc có O (N^2) Edges

cho một đồ thị thưa thớt có O (N) Edges.

hằng là tất nhiên irrelavent cho lớn-O do đó c giọt ra ngoài

Answer 4

Ý nghĩ là trong một đồ thị dày đặc, số cạnh là O (N^2) trong khi trong đồ thị thưa thớt, số lượng các cạnh là O (N). Vì vậy, họ đang dùng O (E \ lg E) và mở rộng nó với xấp xỉ E này để so sánh nó trực tiếp với thời gian chạy của O (N^2) của Prim.

Về cơ bản, nó cho thấy rằng Kruskal là tốt hơn cho đồ thị thưa thớt và Prim là tốt hơn cho các đồ thị dày đặc.

Answer 5

Kruskal là nhạy cảm với số cạnh (E) trong biểu đồ, không phải số lượng nút. Prim tuy nhiên chỉ bị ảnh hưởng bởi số lượng nút (N), đánh giá là O(N^2). Điều này có nghĩa là trong các đồ thị dày đặc, nơi số cạnh tiếp cận N^2 (tất cả các nút được kết nối), hệ số phức tạp của O(E*log(E)) tương đương với O(N^2*log(N)).

C là hằng số để tính đến ký tự 'gần như' và không liên quan đến ký hiệu O. Ngoài ra log (N^2) có cùng thứ tự độ lớn như log (N) vì logarit vượt quá sức mạnh của 2 bởi biên độ đáng kể (log(N^2) => 2*log(N) trong ký hiệu O là O(log(N))).

Trong biểu đồ thưa thớt E gần với N cho bạn O(N*log(N)).

Answer 6

Đầu tiên: n là số đỉnh.

Prim là O (n^2) phần đó đủ dễ dàng.

Kruskal là O (Elog (E)) trong đó E là số cạnh. trong một đồ thị dày đặc, có nhiều như N chọn 2 cạnh, đó là khoảng n^2 (thực sự nó n (n-1)/2, nhưng ai đếm?) Vì vậy, nó là khoảng n^2 log (n^2) là 2n^2 log n là O (n^2logn) lớn hơn O (n^2)

Trong biểu đồ thưa thớt, có ít nhất là n cạnh, vì vậy chúng ta có n log n nhỏ hơn O (n^2).