Cấu trúc dữ liệu và thuật toán #3: BigO Notation và ví dụ | DS&A

É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

[@hoanshiro-jk]

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)

@@hoanshiro-jk ờ 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)

[@hoanshiro-jk]

@ 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

[@MinhTriet1710]

@ e định cmt là anh sai chỗ này mà kéo xuống thì thấy cmt trước r :D

[@hendryhoang2002]

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ứ

[@aiinh8073]

Xịn quá, đọc cuốn Data Structures And Algorithms Made Easy ko hiểu lắm, qua đây cái ổn áp.

[@angnamnguyen541]

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

[@angnamnguyen541]

@ anh còn nhớ em không :v

@@angnamnguyen541 Nghe tên giống thanh niên GPA 3.59 ghê :v

[@angnamnguyen541]

Thôi anh đừng nói vậy =)) anh nhớ em là em vui lắm rồiiii

[@C94-t7n]

Chưa biết j, mà nghe nhìn cuốn quá như học toán ý 😁, xem full video luôn, thanks anh

[@nguyenngocle485]

video series của anh hay quá! mong anh ra những video như này ạ

[@blackswordsman1645]

Bổ ích quá anh! Mong anh làm nhiều video như này hehe

[@hiiamtrong]

Video của anh rất chất lượng, mong anh ra thêm series hơn về DS&A

[@trangdaotdi]

quá tuyệt vời, mọi thắc mắc đã được giải đáp, hahaha

[@theeyesneverlie7451]

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 ạ.

[@uoclethanh2241]

hello ông dev kiến thức này rất hay ạ

[@baonguyengia1563]

Tuyệt vời quá tiền bối, e cảm ơn ak

[@daovanhieu7091]

Hay quá anh ơi

[@hust4189]

Em cảm ơn anh nha

[@bennguyen8327]

nghe đã thực sự

[@ucNguyen-wq2oi]

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

[@quangnguyenkim478]

Nhạc lofi jazz hay quá quên cả nghe anh nói @@

[@nguyennam5056]

Cảm ơn anh

[@vietronaldo23w]

hiểu rồi nhé ông dev :D

[@marcnguyen1512]

15:24 Phải là high = arr.length chứ nhỉ 🤔 Edit: À về đoạn sau a sửa rồi. :v

[@jaytran247]

trong video nay dung con keybaord nao thế b?

[@hoanglai2724]

anh ơi cái theme vscode của a tên là gì vậy ạ ?

[@minhhoangngo1912]

Khó quá! Mà cuốn

[@duynhan9870]

Ô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

[@youngtee_01]

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

[@youngtee_01]

@ em hiểu r ạ. Thank a :D

[@kieuducvu307]

Làm sao các biến hàm trong visual nó highlight màu hay vậy các sếp ?

[@asol5957]

C và N0 mình cần tính nó không vậy anhhh .-.

[@geen160]

hay quá cho em xin link nhạc a dùng trong vid được ko ạ =))

[@freesoftware2529]

âm dc nếu a cho nó chạy nhanh hơn tốc độ ánh sáng

[@MinhHieu87]

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.

[@MinhHieu87]

@ 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

[@DanNugzitpopping]

Cái font chữ khó nhìn lắm.

[@tnam4814]

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 kzbin.info

[@HaMyPham-or3fz]

Bỏ nhạc đi ok hơn ấy ạ

[@anbinh7111]

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 đó.

[@anbinh7111]

@ Dạ cảm ơn anh

[@danhtrancongdanh4495]

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

[@danhtrancongdanh4495]

@ 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 ?

[@HoangfVox]

hiểu, mà là hiểu gì chết liền

[@nhanca4185]

Hello anh

Henlo :D

[@duytran-so6du]

cái font chữ nhìn hơi khó chịu =)))

[@lantrinh5653]

Anh độ em không rớt DSA đi ạ =)))))

Coi series này thì rớt sao nổi :v

[@phamvanhan7037]

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

[@inhdung4729]

nếu theo công thức bạn thì phải là O(n^3) chứ nhỉ

[@letsmile2205]

​@@inhdung4729kết quả cuối cùng phải là O(n^3) chứ, hèn gì xem thấy cấn cấn 😅

[@WilliamLiSci]

Tui thấy buồn ngủ quá