Đây là khóa học đầu tiên của tôi về cấu trúc dữ liệu và mỗi bài giảng/bài giảng TA, chúng tôi nói về O(log(n)). Đây có lẽ là một câu hỏi ngớ ngẩn nhưng tôi đánh giá cao nếu ai đó có thể giải thích cho tôi chính xác những gì nó có nghĩa là gì?Sự khác biệt giữa O (n) và O (log (n)) - cái nào tốt hơn và chính xác là O (log (n)) là gì?
Điều này có nghĩa là quy mô điều tra (thường là thời gian chạy) theo cách phù hợp với logarit của kích thước đầu vào của nó.
Big-O notation không có nghĩa là phương thức chính xác, mà đúng hơn là bị ràng buộc. Ví dụ, đầu ra của các chức năng sau là tất cả O (n):
f(x) = 3x
g(x) = 0.5x
m(x) = x + 5
Bởi vì khi bạn tăng x, kết quả đầu ra của họ tất cả sự gia tăng tuyến tính - nếu có một 6: tỷ lệ 1 giữa f(n) và g(n), có cũng sẽ xấp xỉ tỷ lệ 6: 1 giữa f(10*n) và g(10*n) v.v.
Còn về việc O(n) hoặc O(log n) là tốt hơn, hãy xem xét: nếu n = 1000, sau đó log n = 3 (log-base-10). Mà bạn muốn có thuật toán của bạn để chạy: 1000 giây, hoặc 3 giây?
Được giải thích rõ ràng. Ngoài ra, tôi muốn thêm một số thông tin về những gì một logarit thậm chí là dành cho những người không biết. đăng nhập n trong khoa học máy tính có nghĩa là, số mũ tôi sẽ cần phải nâng số 2 để có được n. Vì vậy, hãy tưởng tượng, nếu n = 16. Số mũ của chúng ta sẽ nhỏ hơn nhiều so với giá trị n thực tế. Nó sẽ là 4. Hy vọng điều này có ý nghĩa. Trong ví dụ trên bằng Amber, cô ấy đưa ra một ví dụ tương tự nhưng tăng 10 lên sức mạnh của 3. –
+1 - Giải thích rõ ràng nhất có thể trong số từ nhỏ nhất. Cảm ơn bạn. – techfoobar
http://en.wikipedia.org/wiki/Big_oh
O (log n) là tốt hơn.
O (logn) có nghĩa là thời gian chạy của thuật toán phụ thuộc vào logarit của kích thước đầu vào. O (n) có nghĩa là thời gian chạy của thuật toán phụ thuộc vào kích thước đầu vào.
về cơ bản, O (cái gì đó) là giới hạn trên trên số hướng dẫn của thuật toán (số nguyên tử). do đó, O (logn) chặt chẽ hơn O (n) và cũng tốt hơn về phân tích thuật toán. Nhưng tất cả các thuật toán là O (logn) cũng là O (n), nhưng không phải ngược ...
"O (n) chặt hơn O (logn) và cũng tốt hơn về phân tích thuật toán" ... rõ ràng O (log (n)) tốt hơn O (n). Tôi nghĩ bạn có nghĩa là cách khác. – LuxuryMode
Silly :) đã chỉnh sửa – Eyal
Đối với đầu vào của kích thước n, một thuật toán của O(n) sẽ thực hiện các bước perportional để n, trong khi một thuật toán của O(log(n)) sẽ thực hiện các bước khoảng log(n).
Rõ ràng log(n) nhỏ hơn n vì vậy thuật toán phức tạp O(log(n)) là tốt hơn. Vì nó sẽ nhanh hơn nhiều.
định nghĩa chính thức:
g (x) = O (f (x)) < => có x0 và liên tục C rằng đối với mỗi x> x0, | g (x) | < = C | f (x) |. Do đó, nếu bạn tìm thấy thuật toán A cho bài toán P, độ phức tạp của nó O (f (n)), bạn có thể nói rằng số bước mà thuật toán của bạn sẽ làm, thấp hơn hoặc bằng tiệm cận với f (n), khi n thường là kích thước đầu vào. (n có thể là bất kỳ điều gì)
Để đọc thêm: http: //en.wikipedia.org/wiki/Big_O_notation.
Sự lặp lại có thể có của http://stackoverflow.com/questions/487258/plain-english-explanation-of-big-o/487278#487278 – sank
Whoa, 1429 upvotes? Tôi sẽ hài lòng với một nửa số đó cho liên kết wikipedia của tôi. –