ฝัง
- เผยแพร่เมื่อ 11 ก.ย. 2024
- Hế lô hế lô, Ông dev đây!
Cấu trúc dữ liệu và thuật toán #3 này mình sẽ nói về BigO Notation và đưa ra một số ví dụ:
- BigO là gì
- BigO để làm gì
- Các thuộc tính trong BigO
- Ví dụ và cách tính BigO
Playlist Thuật toán: • Cấu trúc dữ liệu và th...
Source code: github.com/Ong...
-- Để xem những video về lập trình --
Nhấn vào đây để theo dõi kênh mình nhé: tinyurl.com/Su...
-- Blog của mình --
blog.ongdev.com
-- Ủng hộ Ông Dev --
-- Facebook page của mình --
/ ongdevvuitinh
Cảm ơn các bạn đã quan tâm theo dõi
#ôngdev #DS&A #cấutrúcdữliệuvàthuậttoán
Éc éc chết tui, mất căn bản cấp 1 cmnr -_- Ở phút 9:55
Tính tổng là (n+1)*n/2 nhân số số hạng, không phải khoảng cách nha mn -_-
Đồng thời với việc chúng ta đã tính số lần bằng phép tổng, nên sẽ không có n*() nữa nha.
=> f(n)= (n+1)*n/2 = n^2/2 + n^/2
O(f(n)) = n^2
14:07 return -1 nằm ngoài for nha mọi người.
Tks Đức Nguyễn, phanvan han và Hoan Shiro đã nhắc :D
hi anh, hình như có sự nhầm lẫm ở phần này:
Giả sử:
n = 1 : i = 0 -> j = 0 -> 1 lần => f(1) = 1;
n = 2: i = 0 -> j = 0 -> 2 lần
i = 1 -> j = 1 -> 1 lần => f(2) = 2 + 1 = 3;
n = 3: i = 0 -> j = 0 -> 3 lần
i = 1 -> j = 1 -> 2 lần
i = 2 -> j = 2 -> 1 lần => f(3) = 3 + 2 + 1 = 6;
....
n = n => f(n) = n + (n-1) + ( n -2 ) + ... + 1 = n*(n+1)/2 = (n^2)/2 + n/2
=> O( f(n) ) = O(n^2)
@@hoanshiro833 ờ nhỉ :v không có cái N ở đằng trước, vì mình đã tính ở sau rồi còn gì :v ok e. O(n^2)
@ các video của anh rất hay và ý nghĩa ạ. Chúc anh đạt nhiều niềm vui trong cuộc sống
@ e định cmt là anh sai chỗ này mà kéo xuống thì thấy cmt trước r :D
Tại sao lại phải bỏ n lần của vòng bên ngoài vậy ạ. E tưởng nó vẫn áp dụng quy tắc nhân chứ
Em có thể giải thích cái binary search mà anh giới thiệu sao cho độ phức tạp là log(N) như sau (Tại em thấy trong video anh chưa nói, mong nó giúp ích cho các bạn khác). Việc chạy mỗi lần chia đôi N ở đây thì khi đến lúc dừng vòng lặp, trường hợp xấu nhất sẽ là 2^(step) = N. Lấy loga 2 vế ta được log step(cơ số 2) = log N (cơ số 2) => Xấu nhất sẽ mất log N bước thực hiện thuật toán => O(log(N))
Mình sẽ có 1 video riêng về cái binary search nha :D
@ anh còn nhớ em không :v
@@angnamnguyen541 Nghe tên giống thanh niên GPA 3.59 ghê :v
Thôi anh đừng nói vậy =)) anh nhớ em là em vui lắm rồiiii
Xịn quá, đọc cuốn Data Structures And Algorithms Made Easy ko hiểu lắm, qua đây cái ổn áp.
hay quá anh ơi, nhưng em góp ý chút là những video sau anh giảm âm lượng của cái nhạc nền xuống 1 chút sẽ dễ nghe hơn ạ.
Chưa biết j, mà nghe nhìn cuốn quá như học toán ý 😁, xem full video luôn, thanks anh
video series của anh hay quá!
mong anh ra những video như này ạ
Bổ ích quá anh! Mong anh làm nhiều video như này hehe
Video của anh rất chất lượng, mong anh ra thêm series hơn về DS&A
quá tuyệt vời, mọi thắc mắc đã được giải đáp, hahaha
Em cảm ơn anh nha
hello ông dev kiến thức này rất hay ạ
Video của anh chất lượng thực sự. Mà e nghĩ đoạn 14:07 , return -1 phải ở ngoài vòng for chứ nhỉ
Ờ hè, nằm ngoài chứ :v
Nhạc lofi jazz hay quá quên cả nghe anh nói @@
Tuyệt vời quá tiền bối, e cảm ơn ak
Hay quá anh ơi
15:24 Phải là high = arr.length chứ nhỉ 🤔
Edit: À về đoạn sau a sửa rồi. :v
nghe đã thực sự
hiểu rồi nhé ông dev :D
Có lỗi nhỏ là công thức tính tổng dãy số = ((số đầu + số cuối)* số hạng)/2 anh nhé ^^!
Nhưng lỗi nhỏ này cũng k ảnh hưởng gì đến chất lượng nội dung của video! hehe! (y)
Úi, vậy là Ông Dev mất căn bản cấp 1 cmnr -_- hiu hiu
nếu theo công thức bạn thì phải là O(n^3) chứ nhỉ
@@inhdung4729kết quả cuối cùng phải là O(n^3) chứ, hèn gì xem thấy cấn cấn 😅
Cảm ơn anh
anh ơi cái theme vscode của a tên là gì vậy ạ ?
Cái font chữ khó nhìn lắm.
nếu chạy vòng for từ 0 đến n thì big O của nó là O(N)
nếu chạy vòng for từ 0 đến 10 (10 là const) thì big O của nó là O(1)
nhưng nếu const là 1 lớn, tầm 10tr hoặc 1 tỷ thì có còn gọi là O(1) nữa không? hay có quy định khoảng giới hạn const là từ bao nhiêu trở đi thì tính là O(N) không?
Thực ra "n" ở đây để thể hiện việc tăng số lượng lặp, thì sẽ tăng thời gian tính toán. O(n) nghĩa là thời gian tính toán sẽ tỷ lệ cấp số nhân nếu bạn tăng số lượng vòng lặp. Và nếu bạn có 1 vòng lặp 10 lần, nhưng xử lý rất phức tạp và tốn nhiều thời gian, thì bản chất nó vẫn là O(n). Còn nói về giới hạn chặn dưới, thì là không có nha.
@ nếu như không có chặn dưới thì kể cả c càng cao thì nó vẫn chỉ là O(1). vì bạn có đề cập trong video là độ phức tạp tính khi n -> ∞, trong trường hợp mình hỏi nó không có n
Làm sao các biến hàm trong visual nó highlight màu hay vậy các sếp ?
trong video nay dung con keybaord nao thế b?
hay quá cho em xin link nhạc a dùng trong vid được ko ạ =))
Ông Dev ơi cho em hỏi tại sao phút 10:15 lại +3 +2 +1 vậy ạ ?
Tính tổng từ1 tới n á e
Khó quá! Mà cuốn
C và N0 mình cần tính nó không vậy anhhh .-.
âm dc nếu a cho nó chạy nhanh hơn tốc độ ánh sáng
cái font chữ nhìn hơi khó chịu =)))
em chỉ biết tiếng anh sơ sơ, như những lệch trong code thôi và em rất muốn học về lập trình bên Javas thì có nên trâu dồi kiến thức tiếng anh nhiều k anh
Nên em ạ, dù cho em học cái gì đi nữa thì cũng nên học tiếng Anh nha. Đất nước hội nhập bao lâu rồi, sắp tới toàn công ty đa quốc gia, ko có tiếng Anh sao sống e :v
@ anh cho em hỏi thêm 1 lần nữa, người mới bắt đầu học Javascript thì nên bắt đầu học những cái gì trước ?
22:20 cho em hỏi tsao j=j+2 lại bằng 1 nửa j++ vậy anh?
A có giải thích đó em, j++ là j=j+1. Mỗi vòng lặp tăng 1, + 2 thì mỗi vòng tăng 2. Nên nếu +2 thì số lượng vòng lặp sẽ còn 1 nửa
@ em hiểu r ạ. Thank a :D
anh làm quả beat hay quá! đang tập trung vẫn phải nhún theo nhạc. anh có link nhạc cho em xin ạ!
V Nam mình hay dùng nhạc trên này nha th-cam.com/users/Chillhopdotcom
Bỏ nhạc đi ok hơn ấy ạ
Anh độ em không rớt DSA đi ạ =)))))
Coi series này thì rớt sao nổi :v
Hello anh
Henlo :D
Anh ơi
Có phần 1,2 không
Có nha e, e có thể vào channel để coi cả playlist, hoặc em reload lại video, a mới thêm cái playlist link vào description đó.
@ Dạ cảm ơn anh
hiểu, mà là hiểu gì chết liền
Tui thấy buồn ngủ quá