#7 [C++]. Phân Tích Độ Phức Tạp Của Thuật Toán | Độ Phức Tạp Tính Toán Của Thuật Toán

[@28tech_]

Thông tin các khóa học mình đang hướng dẫn : 28tech.com.vn/

[@Ta-sz2ip]

Công đức vô lượng anh ơi, giảng bài hay và nêu rõ ràng không bỏ qua cho dù dễ hiểu thế nào, đôi lúc người khác giảng bị hiệu ứng lời nguyền kiến thức khiến em bị kẹt chứ ở anh rất thoải mái.

[@28tech_]

Tính ra mình bỏ nhiều phần đấy, chỉ nói phần chính thôi, chứ lan man 1 hồi thì cũng chả đọng lại gì vì lượng thông tin quá nhiều :D

[@Ta-sz2ip]

@@28tech_ thực ra đúng là vậy khi xem vài video khác, nhưng em cảm thấy anh làm video trên tinh thần dạy cho các bạn học có sự tận tâm hơn. Nhiều người làm video dạy về hàm có thể cô đọng trong 10', nhưng mà họ phải có nhiều kiến thức hơn để thực sự hiểu 10' đó, còn người xem chỉ hiểu đc chút thôi. Nhiều thứ tuy nhỏ, nhưng nó lại có điểm chung, bổ sung, đối ứng nhau, hiểu cái này thì mới hiểu cái kia, vậy nên lan man cũng tốt.

[@duynghiem8822]

Bài giảng hay quá ạ

[@28tech_]

C++ mình còn ít về con trỏ vs hướng đối tượng nữa là xong rồi :D

[@duongvankieu4828]

Đánh giá độ phức tạp bài này giúp em với a Procedure binary search (x: nguyên, a1, a2, ... an: các số nguyên tăng dần) i := 1 {i là điểm mút trái của khoảng tìm kiếm} j := n {j là điểm mút phải của khoảng tìm kiếm} while 𝑖 < 𝑗 begin m := (𝑖 + 𝑗)/2 if 𝑥 > 𝑎 𝑚 then i:= m + 1 else j:= m end if x = a then location :=i else location :=0 { location là chỉ số của số hạng bằng x hoặc là 0 nếu không tìm được x}

[@28tech_]

Độ phức tạp của binary search là logN em nhé. Nó cứ chia 2 dần dần mà nên số vòng lặp của thuật toán là log2(n)

[@duongvankieu4828]

@@28tech_còn trường hợp xấu nhất của nó sẽ là gì anh!~~

[@28tech_]

@@duongvankieu4828 logN là xấu nhất rồi đấy.

[@BangNguyen-hd6sk]

link ông làm về thuật toán die rồi a ơi, a post lại ở phần bình luận đi a

[@nightcoretado3877]

hôm nay lại tiếp tục cày

[@HongNhung-dm5zi]

so so grateful for your lesson !

[@thanhh_pham5366]

cho mình hỏi vòng for(i=0,i

[@28tech_]

N^2 đó em

[@KienNguyen-mo3we]

bài giảng của anh hay quá

[@28tech_]

Thank you :D.

[@quangvo2552]

chính thức bắt đầu ngày hôm nay try hard

[@datdang9416]

good job bro, thank you for video

[@hovanhung9802]

Bài giảng hay lắm anhh.Okk:))

[@28tech_]

Ok thank you em đã ủng hộ hehe.

[@zerotwo918]

e học xong c rùi. h wa c++ để học oop. a cho e hỏi trong series này oop là đầy đủ r à anh

[@VietLe-fp7me]

em cảm ơn anh nhiều lắm

[@nguyenhuyhoang8833]

quá ok

[@khanhsb15]

Cảm ơn bạn

[@Vlingn]

Bài này e nghĩ bét nhất nó phải ở sau bài mảng chứ nhỉ ?

[@28tech_]

Học cái C++ này mà muốn học nâng cao rất khó học hết cái này rồi mới tới cái kia em ạ nó thường lẫn

[@ThuyHoang-di4hs]

anh ơi nhiều từ OK quá , nhưng e cảm ơn anh ạ

[@28tech_]

Haha ok. A sẽ rút kinh nghiệm. Nó quen mồm.

[@trung645]

anh ơi hình như còn chia làm độ phức tạp về thời gian và độ phức tạp về tài nguyên sử dụng đúng k ạ?

[@chuitv7035]

while(n%i==0){ n=n/i;dem++} này độ phức tạp là bao nhiêu nhỉ

[@28tech_]

LogN nhé bạn

[@norly_nzn]

anh ơi vậy khi lập trình game vậy mình cần phải học những cái gì ạ, tại em không phải dùng code để học mà là làm game nhưng em vẫn chưa biết phải học cái nào mới đúng????

[@hoangnguyencao58]

C++,C#,java

[@HuyĐạtPhan-o8f]

vi sao a[i] + a[j] > val vậy ạ

[@trunguc6711]

Tại sao căn của n lại được coi là log n được ạ

[@tutosolve]

có vẻ sai chỗ này

[@khanhta-rx2ku]

xong series này đã là tới data structures and algorithms đúng k ạ !

[@28tech_]

Chắc mình sẽ làm Python trước. DSA làm hơi mất thời gian. Series C++ này cũng chứa sắp xếp, tìm kiếm, sinh vs quay lui rồi :D

[@khanhta-rx2ku]

@@28tech_ series này bọn e biết được thêm những cái mới về c và c++, em cảm ơn a nhiều lắm ạ. rất mong sau này a có những content hay như thế ạ. như về mảng js ạ. rất hóng những vid tiếp theo của a!

[@28tech_]

@@khanhta-rx2ku Cảm ơn phản hồi của bạn nhé.

[@NguyenHongQuan_BDCCN]

anh ơi (O logbình n) là ntn ạ, theo anh bảo thì căn n coi là O(log n) vậy O(log ^2 n) là O(n) ạ, em chưa hiểu lắm

[@giapmaitan9844]

seri này học trong bao lâu thì ổn v ad

[@28tech_]

Học tốt thì 3 tháng, bình thường thì 5 6 tháng, học không cẩn thận thì mấy năm cũng không hết :D

[@kaito66662]

for (int i = 0; i < n; i++) { // 2 + (1 + 1 + A)n + 1 for (int j = i + 1; j < n; j++) { // A = 3 + 13(n - 1) + 1 if (a[i] > a[j]) { int t = a[i]; a[i] = a[j]; a[j] = t; } } } anh cho em hỏi với ạ xác định số phép toán của cái này như nào ạ hôm đấy em đi học muộn không kịp nghe giảng đoạn đầu chỉ kịp code lại trên bảng

[@zinzii2990]

anh ơi câu này tính độ phức tạp thì như thế nào : void in(int k) { cout

[@thuatvan6245]

Gcd(ll a,ll b ) ấy ạ

[@28tech_]

ah hàm này là hàm ước chung lớn nhất nhé em :D, còn lcm là hàm bội chung nhỏ nhất.

[@thuatvan6245]

@@28tech_ dạ e cảm ơn nhiều ạ

[@khongbietnam]

ok

[@28tech_]

@@khongbietnam ok luôn 🤭

[@tambui7728]

Nếu mà em có 2 vòng for riêng biệt Vòng for1 chạy từ 1 đến sqrt(n) Vòng for2 chạy từ sqrt(n) đến n Thì độ phức tạp là O(logn) hayO (n) thế anh

[@28tech_]

Tích độ phức tạp của 2 vòng for em.

[@tambui7728]

@@28tech_ ok anh

[@nhatphamhong4183]

n+m nha

[@SPK-Alast]

Phân tích độ phức tạp để làm gì vậy ạ

[@taynguyenduongchanh1575]

Để chọn thuật toán cho tối ưu đấy. 1 bài có nhiều cách giải, mỗi cách giải có 1 độ phức tạp riêng. K phân tích chọn bừa nếu input nó cao + chọn cách giải ví dụ 2 vòng for lồng nhau độ phức tạp là O(n^2) thì ăn TLE vào mồm

[@inhhuuan6042]

Series C++ này đã bao gồm các bài hướng đối tượng và cấu trúc dữ liệu rồi đúng ko ạ?

[@28tech_]

Có 1 số ctdl rồi e. Em có thể xem qua nội dung playlist bên dưới

[@vuhoang6968]

ô kê

[@28tech_]

Oke 🤟

[@thuatvan6245]

cho em hỏi phút 4:43 dòng 30 tại sao i

[@28tech_]

Code như vậy nó ko tối ưu.

[@thuatvan6245]

@@28tech_ dạ em hiểu r ạ

[@hieuthach9391]

cái phân tích độ phức tạp này để làm gì vậy anh ?

[@28tech_]

Để biết thuật toán của mình có tốt hay không em ạ

[@nguoicuacongchung9962]

hình như a lạm dụng từ OK hơi nhiều đấy anh

[@28tech_]

Oke em 🤗🤗🤗. Giờ hết rồi

[@chatGPT-ni7gx]

cho em hỏi tại sao video của anh cứ bị rè rè á

[@thuatvan6245]

gcd lcm có tác dụng gì vậy ạ

[@28tech_]

Ý em hỏi là gì nhỉ?

[@phanhonghanhbtechn7228]

ok ok

[@28tech_]

Oke 😆😆😆

[@CongNguyen-fi5cd]

học này để lmj v a

[@28tech_]

Học để biết mình code có tốt hay không?

[@hplat-vku]

mấy bác học code có ghi chép gì không, hay chỉ làm ví dụ cho dễ nhớ

[@doncream2908]

có dùng // kế bên cái ví dụ để note

[@hplat-vku]

@@doncream2908 thank bác ạ, kiểu em sợ quên mấy đoạn code. Thôi thì cứ làm nhiều là nhớ bác nhỉ

[@trankhanh2320]

O(căn n) sao bằng )(log n ) vậy anh

[@28tech_]

Chính xác thì là O(can n) nhé em. A hay quy chung logN 😇

[@nguyenuckhoi8627]

Sao O(log n) lại bằng O(sqrt(n)) vậy?

[@28tech_]

@@nguyenuckhoi8627 chuẩn thì là O(logN) nha em

[@LienLe-rh3dl]

anh ơi với câu này độ phức tạp thì sao anh ? int gcd(int a, int b) { int p = 0; while (b != 0) { p = a % b; a = b; b = p; } return a; }

[@28tech_]

Gcd dpt la o(log(min(a,b))

[@LienLe-rh3dl]

@@28tech_ em cảm on anh

[@chuitv7035]

Em để là O(log(n)) được không anh

[@ngoile876]

a ơi, cho e hỏi: Nhập vào một biễu thức toán học dạng chuỗi bao gồm phép cộng và phép nhân Tính giá trị của biểu thức đó. vi du: input: "234*345*34+88+56*56+45+6*4" output: 2748113 bài này mình xử lý như nào vậy a

[@28tech_]

Này em phải học cách tính toán giá trị biểu thức trung tố nhé. Tìm từ khoá evaluate infix expression geeksforgeeks

[@ngoile876]

@@28tech_ ôi e c.on a ạ, tại e gặp bài này e lại nghĩ theo hướng C khi a cho e keyword thì e mới biết đó là C++

[@28tech_]

@@ngoile876 c cũng được mà nhưng khó code lắm

[@tgjang4947]

tác dụng của cái O() này là sao ạ

[@28tech_]

Nó là kí hiệu thôi e. Big O Notation

[@HaiDang_23]

-1e9 là sao ạ

[@28tech_]

IT PTIT năm mà toang thế e. -10^9 nhé e

[@HaiDang_23]

@@28tech_ dốt quá a ạ😞😞. May có kênh này cứu cánh

[@tranthienphuc8543]

với câu như thế này thì độ phức tạp phải tính như thế nào z anh ? void printone (int a[]){ for(i = 0; i0 ;j - - ){ if(a[i ] == a[ j ]) f=1; } if(f == 0) printf("%d" , a[ i ]); } }

[@28tech_]

Vẫn là O(n^2) nhé, mặc dù vòng for con trong lặp ít hơn :D,

[@tranthienphuc8543]

@@28tech_ anh có thể giải chi tiết giúp em như trong video anh đã làm đc ko tại vì phần độ phức tạp của thuật toán, nếu như chỉ nói kết quả cuối cùng thì nó không đủ để chứng minh đc, em cũng đang vướng mắc phần này và gặp đúng bài này nên em cũng chả biết phải tìm thời gian thực hiện của các câu lệnh như thế nào nữa. Nếu như ở vòng for trên thì nó quá rõ ràng để xác định đc số lần lặp, nhưng ở vòng for dưới việc tìm số lần là rất khó do i có 2 trường hợp là 0 hoặc 1 thì nó ko lặp mà muốn xây dựng một công thức tính số lần lặp tổng quát cho câu dưới thì em lại ko biết. Mong anh có thể giúp đỡ em đc ko

[@hungtruong7812]

Sao m*n =n*2