Ai đó có thể giải thích cho tôi một cách đơn giản tại sao hằng số không quan trọng khi nói đến ký hiệu O lớn? Tại sao sự phức tạp vẫn giữ nguyên khi bạn thêm một hằng số. Đây không phải là một bài tập về nhà tôi chỉ muốn hiểu điều này tốt hơn. Hãy để tôi có được O thẳng lớn này là để xem hành vi của một hàm khi nó tiến tới vô cùng đúng không?Mức độ phức tạp. Tại sao không hằng số vấn đề?
Tôi hiểu rồi. Cảm ơn rất nhiều người.
Nó không quan trọng cho lý thuyết phức tạp, mà là quan tâm chỉ trong cách chức năng quy mô như kích thước đầu vào phát triển.
Hằng số không ảnh hưởng đến cách hoạt động của chức năng như kích thước đầu vào phát triển theo hướng vô cực.
Tuy nhiên, nếu bạn quan tâm đến việc thực sự chạy một đoạn mã nhất định, bạn có thể rất quan tâm đến chi phí không đổi lớn và cách thực hiện chức năng cho các kích thước đầu vào nhỏ hơn.
Sự khác biệt giữa lý thuyết phức tạp và thực tiễn.
Ký hiệu Big-O là cách sử dụng tài nguyên (thời gian, bộ nhớ) thay đổi khi số lượng mục thay đổi. Vì vậy, ví dụ, nếu máy tính của tôi có thể sắp xếp 10 mục trong 1 giây, 20 mục trong 4 giây và 30 mục trong 9 giây, thì đó là O (n ²).
Nếu tôi có thể sắp xếp các mục tương tự bằng tay trong 10 giây, 40 giây và 90 giây tương ứng, thì tôi vẫn là O (n ²), nhưng yếu tố không đổi của tôi lớn gấp 10 lần: đưa tôi mười lần miễn là máy tính.
Câu trả lời là ... theo định nghĩa. Nếu một số chức năng f(x) là lớn-O của một số chức năng g(x), nó chỉ có nghĩa là f(x) là "cuối cùng" nhỏ hơn một số lần liên tục g(x). (ví dụ: đủ lớn x). Giá trị thực tế của hằng số không quan trọng; cũng như vị trí của hành vi "cuối cùng" - miễn là nó đúng cho một đủ lớn x và một hằng số đủ lớn, bạn được bảo hiểm.
Bạn có thể thêm vào hằng số hoặc bất kỳ thứ gì có chữ O nhỏ hơn và không quan trọng - tất cả đều tăng nhanh nhất và cụm từ nào chiếm ưu thế là x tăng.
Big O giải thích mức độ phức tạp thay đổi khi đầu vào lớn. Đầu vào của bạn càng lớn thì càng có ít hằng số quan trọng hơn. Ví dụ, nhân một cái gì đó bằng 10 là ít quan trọng hơn nhiều so với bình phương một cái gì đó khi n được một triệu hoặc một tỷ. Big O không phải là một phép đo chính xác, đó là một cách để đưa thuật toán của bạn vào một lớp phức tạp thô ráp để bạn có thể làm tròn các hằng số vì chúng không có ý nghĩa với các giá trị n lớn.
Trong thực tiễn, đôi khi hằng số làm vấn đề. Nhưng, khi chúng ta nói về ký hiệu Big O, chúng ta đang nhìn vào hành vi tiệm cận. Lý do hằng số không ảnh hưởng đến hành vi tiệm cận là vì hàm có đường cong phát triển nhanh hơn sẽ là luôn luôn vượt qua một hàm có đường cong phát triển chậm hơn ngay cả khi có hằng số rất lớn (mặc dù sẽ mất nhiều thời gian hơn để đến đó, tất nhiên).
Vì vậy, chúng tôi nói rằng hằng số "không quan trọng", bởi vì nó không bao giờ có thể thay đổi mối quan hệ tiệm cận giữa các đường cong.
Hằng số không quan trọng trong ký hiệu big-O vì mối quan tâm là khả năng mở rộng.
trừ khi bạn muốn giảm tỷ lệ ... – Thilo
Do hằng số độc lập với N: nó không thay đổi, tức là nó không đổi. –