Helpex - Trao Đổi & Giúp Đỡ - là một trang web chia sẻ kiến thức và hỏi đáp dành cho các lĩnh vực ở mọi cấp độ và các chuyên gia trong các lĩnh vực liên quan. Chỉ mất một phút để đăng ký.
Tham gia cộng đồng
Với sự tham khảo của câu trả lời này , Theta (ràng buộc chặt chẽ) là gì?
Omega bị ràng buộc thấp hơn, khá dễ hiểu, thời gian tối thiểu mà một thuật toán có thể mất. Và chúng ta biết Big-O dành cho giới hạn trên, có nghĩa là thời gian tối đa mà thuật toán có thể mất. Nhưng tôi không có ý tưởng liên quan đến Theta.
Big O là giới hạn trên, trong khi Omega là giới hạn dưới. Theta yêu cầu cả Big O và Omega, vì vậy đó là lý do tại sao nó được gọi là giới hạn chặt chẽ (nó phải là cả giới hạn trên và dưới).
Ví dụ, một thuật toán Omega(n log n)mất ít nhất n log nthời gian, nhưng không có giới hạn trên. Một thuật toán lấy Theta(n log n)được ưu tiên hơn nhiều vì nó mất ít nhất n log n (Omega n log n) và không nhiều hơn n log n (Big O n log n).
Θ-ký hiệu (theta ký hiệu) được gọi là chặt chẽ-bound vì nó chính xác hơn O-ký hiệu và Ω-ký hiệu (ký hiệu omega).
Nếu tôi lười biếng, tôi có thể nói rằng tìm kiếm nhị phân trên một mảng được sắp xếp là O (n 2 ), O (n 3 ) và O (2 n ), và tôi sẽ đúng về mặt kỹ thuật trong mọi trường hợp. Đó là bởi vì ký hiệu O chỉ xác định giới hạn trên và tìm kiếm nhị phân được giới hạn ở phía cao bởi tất cả các chức năng đó, chỉ là không chặt chẽ lắm. Những ước tính lười biếng sẽ là vô ích .
Ký hiệu sol giải quyết vấn đề này bằng cách kết hợp ký hiệu O và ký hiệu .. Nếu tôi nói rằng tìm kiếm nhị phân là (log n), điều đó cung cấp cho bạn thông tin chính xác hơn. Nó cho bạn biết rằng thuật toán được giới hạn ở cả hai phía bởi hàm đã cho, vì vậy nó sẽ không bao giờ nhanh hơn hoặc chậm hơn đáng kể so với đã nêu.
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every case- Có vẻ như hầu hết mọi người trong thế giới máy tính chỉ lười biếng vì mọi người chủ yếu chỉ nói về sự phức tạp của Big O mà thôi.
If I were lazy, I could say that binary search on a sorted array is O(n2), O(n3), and O(2n), and I would be technically correct in every caseTrong trường hợp ai đó nhầm lẫn với điều này: Đối với loại chức năng không chặt chẽ không có ký hiệu nhỏ, ký hiệu o nhỏ được sử dụng. Ví dụ: - Ràng buộc 2n ^ 2 = O (n ^ 2) chặt chẽ không có triệu chứng, nhưng ràng buộc 2n = O (n ^ 2) thì không. Đọc thêm: stackoverflow.com/questions/1364444/
Nếu bạn có cái gì đó là O (f (n)) mà có nghĩa là có được k , g (n) mà f (n) ≤ kg (n) .
Nếu bạn có cái gì đó là Ω (f (n)) mà có nghĩa là có được k , g (n) mà f (n) ≥ kg (n) .
Và nếu bạn có một cái gì đó với O (f (n)) và (f (n)) , thì đó là Θ (f (n) .
Các bài viết Wikipedia là phong nha, nếu một chút dày đặc.
Bây giờ đọc gia đình của ký hiệu Bachmann-Landau. Cảm ơn Charlie, tôi đã đến đó trước đó, nhưng đã trở lại mà không tiến tới chiều dài của nó.
– Hoàng Tuyết Xuân 04:38:22 21/01/2009Hey, thật tốt khi được làm mới trên comps tiến sĩ thường xuyên.
– Hồ Hương Giang 17:30:30 21/01/2009Lưu ý rằng ký hiệu big-O của Landau không giới hạn ở độ phức tạp thuật toán.
– Hồ Vĩnh Ân 15:00:51 20/02/2015Điều này có vẻ sai. Trong dòng đầu tiên, nó nên đọc "Nếu bạn có một cái gì đó là O (g (n))", nghĩa là, gthay vì f, và phần còn lại có thể được để nguyên như vậy. Tương tự với dòng thứ hai: nó phải là "Nếu bạn có thứ gì đó (g (n))". Bạn có thể vui lòng kiểm tra lại?
Toàn bộ chủ đề rất lộn xộn đến nỗi ai đó có uy tín đó cũng có thể hiểu sai: D Đùa sang một bên, ai đó cần sửa câu trả lời này. Điều này làm mọi người bối rối (nó đã làm tôi rất nhiều).
– Trịnh Băng Tâm 08:46:09 19/04/2019Giới hạn trên tiệm cận có nghĩa là một thuật toán nhất định thực thi trong khoảng thời gian tối đa, tùy thuộc vào số lượng đầu vào.
Hãy lấy một thuật toán sắp xếp làm ví dụ. Nếu tất cả các phần tử của một mảng theo thứ tự giảm dần, thì để sắp xếp chúng, sẽ mất một thời gian chạy O(n), cho thấy độ phức tạp giới hạn trên. Nếu mảng đã được sắp xếp, giá trị sẽ là O(1).
Nói chung, O-notationđược sử dụng cho sự phức tạp ràng buộc trên.
Tiệm ràng buộc chặt chẽ (c 1 g (n) ≤ f (n) ≤ c 2 g (n)) cho thấy sự phức tạp cam kết bình quân cho một chức năng, có giá trị giữa, giới hạn (giới hạn trên và dưới bị ràng buộc), trong đó c 1 và c 2 là hằng số.
Các cụm từ thời gian tối thiểu và thời gian tối đa là một chút sai lệch ở đây. Khi chúng ta nói về các ký hiệu O lớn, đó không phải là thời gian thực sự chúng ta quan tâm, đó là cách thời gian tăng lên khi kích thước đầu vào của chúng ta lớn hơn. Và đó thường là thời gian trung bình hoặc tồi tệ nhất mà chúng ta đang nói đến, không phải là trường hợp tốt nhất , thường không có ý nghĩa trong việc giải quyết các vấn đề của chúng ta.
Sử dụng tìm kiếm mảng trong câu trả lời được chấp nhận cho câu hỏi khác làm ví dụ. Thời gian cần thiết để tìm một số cụ thể trong danh sách kích thước n là n / 2 * some_constant trung bình. Nếu bạn coi nó như một chức năng f(n) = n/2*some_constant, nó sẽ tăng không nhanh hơn g(n) = n, theo nghĩa được đưa ra bởi Charlie. Ngoài ra, nó tăng không chậm hơn g(n)một trong hai. Do đó, g(n)thực sự là cả giới hạn trên và giới hạn dưới của f(n)ký hiệu Big-O, vì vậy độ phức tạp của tìm kiếm tuyến tính chính xác là n , có nghĩa là nó là Theta (n).
Về vấn đề này, lời giải thích trong câu trả lời được chấp nhận cho câu hỏi khác không hoàn toàn chính xác, điều này cho rằng O (n) bị ràng buộc bởi vì thuật toán có thể chạy trong thời gian không đổi đối với một số đầu vào (đây là trường hợp tốt nhất tôi đã đề cập ở trên, đó không thực sự là những gì chúng ta muốn biết về thời gian chạy).
Vì vậy, chúng ta có thể nói rằng là trường hợp tốt nhất và O là trường hợp xấu nhất?. . .. và chúng ta có nên thay thế các điều khoản như trường hợp tốt nhất và trường hợp xấu nhất tương ứng không?
– Hoàng Tuyết Xuân 05:06:46 21/01/2009@Adeel, không, Theta và O đều có thể đề cập đến trường hợp trung bình hoặc trường hợp xấu nhất. @Zach, tốt, không chính xác. Cảm ơn đã chỉ ra rằng.
– Hồ Vĩnh Ân 05:33:11 21/01/2009Sự khác biệt cơ bản giữa
Blockquote
Asym.upperbound bị ràng buộc trên không có triệu chứng và chặt chẽ không có triệu chứng có nghĩa là một đại số nhất định có thể thực hiện với lượng thời gian tối đa tùy thuộc vào số lượng đầu vào, ví dụ như sắp xếp algo nếu tất cả các phần tử mảng (n) theo thứ tự giảm dần sẽ mất một thời gian chạy O (n) cho thấy độ phức tạp giới hạn trên, nhưng nếu chúng đã được sắp xếp thì sẽ mất ohm (1). Vì vậy, chúng ta thường sử dụng ký hiệu "O" cho độ phức tạp giới hạn trên.
Asym. ràng buộc chặt chẽ cho thấy ví dụ (c1g (n) <= f (n) <= c2g (n)) cho thấy giới hạn ràng buộc chặt chẽ sao cho hàm có giá trị ở giữa hai giới hạn (giới hạn trên và giới hạn dưới), đưa ra trường hợp trung bình.
Bạn không nên trả lời các câu hỏi cũ nếu câu trả lời của bạn không thêm bất kỳ câu nào vào câu trả lời đã được chấp nhận.
– Hoàng Tuyết Xuân 11:47:54 21/10/2012Nếu tôi lười biếng, tôi có thể nói rằng tìm kiếm nhị phân trên một mảng được sắp xếp là O (n2), O (n3) và O (2n), và tôi sẽ đúng về mặt kỹ thuật trong mọi trường hợp.
Chúng ta có thể sử dụng ký hiệu o ("little-oh") để biểu thị một giới hạn trên không chặt chẽ về mặt không có triệu chứng. Cả big-oh và little-oh đều giống nhau. Nhưng, big-oh có khả năng được sử dụng để xác định giới hạn trên chặt chẽ không có triệu chứng.
Oh .. Bây giờ thuật ngữ "ràng buộc chặt chẽ" xuất hiện khá tự giải thích với tôi. Cảm ơn Chris. Ngu ngốc, có lẽ tôi đã mong đợi một ý tưởng phức tạp. :)
– Hoàng Tuyết Xuân 04:35:51 21/01/2009Phải, có rất nhiều ký hiệu lạ mắt được ném xung quanh nhưng nó không quá phức tạp một khi bạn đặt nó dưới thắt lưng của mình.
– Hồ Hương Giang 04:37:48 21/01/2009Tài liệu có sẵn miễn phí này từ Virginia Tech giải thích với các ví dụ về sự khác biệt về hiệu suất giữa các thuật toán có độ phức tạp khác nhau và giải thích ngắn gọn Phân tích tiệm cận: people.cs.vt.edu/shaffer/Book/C++3e20120102.pdf
– Hồ Vĩnh Ân 09:14:31 26/02/2016Ý bạn là gì khi "Thuật toán lấy Theta (n log n) được ưu tiên hơn nhiều vì phải mất ít nhất n log n (Omega n log n) và không nhiều hơn n log n (Big O n log n).", Như trong, đó có phải là độ phức tạp chính xác của một thuật toán như bạn đã nói ít nhất là Omega (nlogn) và tối đa BigO (nlogn) không?
– Tạ Nhân Văn 21:26:39 07/07/2016@NikhilVerma Không phải câu trả lời của hóa đơn dưới đây bao gồm bạn?
– Trịnh Băng Tâm 21:12:41 30/07/2016