Chủ Nhật, Tháng Sáu 13, 2021
spot_img
Trang chủKiến ThứcHỏi ĐápN Sao Là Gì - Số Tự Nhiên Là Gì

N Sao Là Gì – Số Tự Nhiên Là Gì

Đôi khi tôi thấy (n) với biểu tượng strange lạ với một cái gì đó ở giữa nó, và đôi khi chỉ là O (n). Có phải chỉ là sự lười biếng khi gõ bởi vì không ai biết cách gõ biểu tượng này, hoặc nó có nghĩa gì đó khác nhau?

Giải thích ngắn gọn:

Nếu một thuật toán là (g (n)), điều đó có nghĩa là thời gian chạy của thuật toán khi n (kích thước đầu vào) lớn hơn tỷ lệ với g (n).

Đang xem: N sao là gì

Nếu một thuật toán là O (g (n)), nó có nghĩa là thời gian chạy của thuật toán như n được lớn hơn là nhiều nhất là tỷ lệ thuận với g (n).

Thông thường, ngay cả khi mọi người nói về O (g (n)) họ thực sự có nghĩa là Θ (g (n)) nhưng về mặt kỹ thuật, có một sự khác biệt.

Kỹ thuật hơn:

O (n) đại diện cho giới hạn trên. (N) có nghĩa là ràng buộc chặt chẽ. (N) đại diện cho giới hạn dưới.

f (x) = Θ (g (x)) iff f (x) = O (g (x)) và f (x) = Ω (g (x))

Về cơ bản khi chúng ta nói một thuật toán là của O (n), thì nó cũng là O (n 2 ), O (n 1000000 ), O (2 n ), … nhưng thuật toán (n) không phải là Θ (n 2 ) .

Xem thêm: 06 Điểm Bán Gạo Nàng Thơm Chợ Đào Chính Gốc, Gạo Nàng Thơm… Hết Thơm

Trong thực tế, vì f (n) = Θ (g (n)) có nghĩa là cho các giá trị đủ lớn của n, f (n) có thể được ràng buộc trong phạm vi c 1 g (n) và c 2 g (n) cho một số giá trị của c 1 và c 2 , tức là tốc độ tăng trưởng của f là tiệm bằng g: g có thể là một ràng buộc thấp và một giới hạn trên của f. Điều này trực tiếp ngụ ý f có thể là giới hạn dưới và giới hạn trên của g là tốt. Hậu quả là,

f (x) = Θ (g (x)) iff g (x) = Θ (f (x))

Tương tự, để hiển thị f (n) = Θ (g (n)), đủ để hiển thị g là giới hạn trên của f (tức là f (n) = O (g (n))) và f là giới hạn dưới của g (tức là f (n) = Ω (g (n)) là điều tương tự chính xác như g (n) = O (f (n))). Chính xác,

f (x) = Θ (g (x)) iff f (x) = O (g (x)) và g (x) = O (f (x))

Ngoài ra còn có các ωký hiệu little-oh và little-omega ( ) đại diện cho giới hạn trên và dưới lỏng lẻo của một chức năng.

Để tóm tắt:

f(x) = O(g(x))(big-oh) có nghĩa là tốc độ tăng trưởng của f(x)tiệm cận nhỏ hơn hoặc bằng với tốc độ tăng trưởng của g(x).

f(x) = Ω(g(x))(big-omega) có nghĩa là tốc độ tăng trưởng của không f(x)có triệu chứng lớn hơn hoặc bằng tốc độ tăng trưởng củag(x)

f(x) = o(g(x))(little-oh) có nghĩa là tốc độ tăng trưởng của không f(x)có triệu chứng thấp hơn tốc độ tăng trưởng của g(x).

Xem thêm: Cách Làm Món Sườn Ngon – 4 Cách Chế Biến Sườn Dân Dã Mà Ngon

f(x) = ω(g(x))(little-omega) có nghĩa là tốc độ tăng trưởng của không f(x)có triệu chứng lớn hơn tốc độ tăng trưởng củag(x)

f(x) = Θ(g(x))(theta) có nghĩa là tốc độ tăng trưởng của f(x)tiệm cận bằng với tốc độ tăng trưởng củag(x)

Để thảo luận chi tiết hơn, bạn có thể đọc định nghĩa trên Wikipedia hoặc tham khảo sách giáo khoa cổ điển như Giới thiệu về thuật toán của Cormen et al.

RELATED ARTICLES

BÌNH LUẬN

Vui lòng nhập bình luận của bạn
Vui lòng nhập tên của bạn ở đây

Most Popular

Recent Comments