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.

12 Likes

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

1 Like

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 :smiley:

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

3 Likes

ừ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

2 Likes

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ả

1 Like

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

3 Likes

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…:sob:

3 Likes

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 ? :grinning:

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

2 Likes

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 :smiley:

2 Likes

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

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

2 Likes

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.

1 Like

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 :smiley:

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

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

Ngoài ra mỗi trường hợp best, average, worst đều có Omega và O riêng.

3 Likes

Khi đã viết thành thuật toán thì gần như là theta luôn, vì thế nên đây là ví dụ sử dụng Omega và O.

Chứng minh Fibonacci(n) có theta(n) chữ số (n > 0):

Với n >= 3, Fibo(n) > Fibo(n-1) nên Fibo(n+1) < 2Fibo(n).
Lập dãy u[n] = Fibo(n+3) và v[n] = 2v[n-1], v[0] = Fibo(3). Dễ thấy v[n] = theta(2^n) và u[n] <= v[n] nên Fibo(n) = O(2^n).

Tương tự, Fibo(n+1) > 2Fibo(n-1). Xét dãy w[n] = 2w[n-2], w[0] = Fibo(3) = 2, w[1] = Fibo(4) = 3. Dễ thấy w[n] = theta(2^(n/2)) và u[n] >= w[n] nên Fibo(n) = Omega(căn(2^n))

Lấy log của v[n] <= u[n] <= w[n] thu được đpcm.

2 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?