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

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

[@hoanshiro833]

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)

[@hoanshiro833]

@ 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

[@harrybin1201]

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ứ

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

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

[@marcnguyen1512]

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

[@aiinh8073]

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

[@duytran-so6du]

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

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

[@WilliamLiSci]

Tui thấy buồn ngủ quá

[@hoanglai2724]

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

[@minhhoangngo1912]

Khó quá! Mà cuốn

[@trangdaotdi]

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

[@blackswordsman1645]

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

[@lantrinh5653]

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

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

[@geen160]

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

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

[@nguyenngocle485]

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

[@quangnguyenkim478]

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

[@DanNugzitpopping]

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

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

[@hiiamtrong]

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

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

[@asol5957]

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

[@kieuducvu307]

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

[@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 😅

[@jaytran247]

trong video nay dung con keybaord nao thế b?

[@HoangfVox]

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

[@HaMyPham-or3fz]

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

[@hust4189]

Em cảm ơn anh nha

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

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

[@freesoftware2529]

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

[@vietronaldo23w]

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

[@nguyennam5056]

Cảm ơn anh

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

[@bennguyen8327]

nghe đã thực sự

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

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

[@nhanca4185]

Hello anh

Henlo :D