01/10/2018, 01:17

Bị gấu bỏ vì không biết Big O là gì

Bài viết này là câu chuyện thật của mình, hy vọng nhận được sự góp ý của mọi người.

Vì bài dài và đỡ mất công chỉnh sửa lại nên mình xin được chia sẻ link.

NIVIKI.COM – 16 Jan 17

Bị gấu bỏ vì không biết Big O là gì

“ Big O là gì vậy anh?” “Để đo độ phức tạp của thuật toán đó em” - Tôi vuốt ve mái tóc nàng và trả lời. “Ủa vậy đơn vị là gì anh, công thức tính sao?”

Người bí ẩn viết 03:32 ngày 01/10/2018

Đắng lòng thật :v
Cảm ơn anh đã chia sẽ bài viết

rogp10 viết 03:32 ngày 01/10/2018

Thớt đang mô tả big-theta chứ không phải big-O. Thực ra big-O có thể sử dụng trong các công thức xấp xỉ như:
ln(1 + x) = 0 + x - x^2 + O(x^3) (x -> 0)
đánh giá: lim(x -> 0)(ln(1+x) / x) = lim(x -> 0)(0 + x + O(x^2)) / x = lim(x -> 0)(1 + O(x)) = 1

Trong đánh giá thuật toán ta cho x -> +inf.

Nguyễn Văn Khoa viết 03:32 ngày 01/10/2018

ừa, trong bài viết mình có nói là học thuật thì người ta phân rõ ra Big O với Big Theta. Nhưng để dễ trao đổi trong đời sống thì gộp 2 cái lại với nhau

Đỗ Nhiên viết 03:27 ngày 01/10/2018

chắc cô ý chỉ đùa yêu gái cùng ngành nó khổ thế đây anh à thế nào em ko bao giờ yêu gái cùng ngành cà mặc dù chưa yêu ai cả

明玉 viết 03:27 ngày 01/10/2018

Sau này bạn làm cả Độ Phức tạp Không gian nhé

Tynk Huynk viết 03:20 ngày 01/10/2018

Cái cô này cũng nhảm, đâu phải IT thì cái gì cũng thông tường hết đâu.
Nhìn lại thấy hoàn cảnh giống mình, thằng bạn nó hỏi: làm sao hack nick Facebook của người khác ??
Mình bí, nó phán câu: Học IT mà ko biết cái vụ này hả ?
Ôi, cuộc đời của 1 thằng IT…

Tynk Huynk viết 03:19 ngày 01/10/2018

Cái phần Giữ lại đại lượng lớn nhất ấy anh, đáng lẽ biểu thức trên rút gọn lại là O(N^2) chứ đúng không anh @VanKhoa ?

cdxf viết 03:27 ngày 01/10/2018

hư cấu thế mà bạn vẫn tin à

rogp10 viết 03:26 ngày 01/10/2018

Câu đó thì từ biết sơ sơ, tới nắm cặn kẽ (mấy course), tới làm được PoC là cả 1 quãng đường dài

Nguyễn Văn Khoa viết 03:34 ngày 01/10/2018

cảm ơn bạn, lỗi typo để mình gõ lại

Anh Khoa Nguyen viết 03:26 ngày 01/10/2018

Cái này độ phức tạp con gái

Nguyễn Văn Khoa viết 03:23 ngày 01/10/2018

Cái này độ phức tạp con gái

Thực ra cả bài không liên quan gì đến con gái cả, tựa để chỉ để lôi cuốn người đọc thôi. Toàn bài tập trung vào giải thích định nghĩa Big O theo cách dễ hiểu.

Trần Ngọc Khoa viết 03:32 ngày 01/10/2018

Comment trước khi đọc bài một xíu: Big O là trường hợp xấu nhất (upper bound), còn có một cái là Big Omega là trường hợp tốt nhất (lower bound).
Hy vọng đúng

rogp10 viết 03:22 ngày 01/10/2018

Không đúng Nói ví von thì nó ntn:

  • Big O là <=
  • Little O là <
  • Big Theta là ==
  • Big Omega là >=

Ngoài ra best, average hay worst case phải ghi riêng

Bài liên quan
0