Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Đỗ Ngọc Như Loan

Bài giảng "Cấu trúc dữ liệu và giải thuật - Chương 1: Tổng quan về cấu trúc dữ liệu & giải thuật" cung cấp cho người học các kiến thức: Độ phức tạp của thuật toán, biểu diễn thời gian chạy bởi ký hiệu O. Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Đỗ Ngọc Như LoanGV:ĐỗNgọcNhưLoanCấutrúcdữliệulàgì?CấutrúcdữliệulàcáchtổchứclưutrữdữliệusaochohiệuquảnhấtThếnàolàhiệuquả?1.Chínhxác2.Dùngítbộnhớ3.Khảnăngtìmkiếm/truyxuất4.Khảnăngcậpnhật,thêm(modification,insertion/deletion)5.Đơngiản,dễhiểuGiảithuậtlàgì?Thuậttoánlàmộtphươngphápbaogồmmộtdãycácbướctínhtoánđểgiảiquyếtmộtbàitoán.Thuậttoáncóthểđượcdiễntảdướingônngữtựnhiên(tiếngViệt,tiếngAnh…),mãgiảhayngônngữlậptrình(C++,Java…)Thếnàolàmộtthuậttoántốt?1.Đúngđắn2.Nhanh3.Ítbộnhớ4.Đơngiản,dễhiểuVídụTìmxtrongdãya1,a2,....,anInput:Sốx,dãynsốa1,a2,...,anOutput:MộtgiátrịlogictruehoặcfalseSearch(x,a,n)fori1ton doifai=x thenreturntruereturnfalseMộtvấnđềcóthểđượcgiảiquyếtbẳngnhiềuthuậttoánkhácnhauVídụTínhtổngcácsốnguyêntừ1đếnn.Input:n(n>1)Output:Tổngcácsốnguyêntừ1đếnnCách1sum=0;for(inti=1;i ĐộphứctạpCách1 O(n)sum=0;for(inti=1;iĐỘPHỨCTẠPTHUẬTTOÁNĐộphứctạpcủagiảithuậtlàchiphívềtàinguyêncủahệthống(chủyếulàthờigian,bộnhớ,CPU,đườngtruyền)cầnthiếtđểthựchiệngiảithuật Độphứctạpvềkhônggian(dunglượngbộ nhớsửdụng) ĐộphứctạpvềthờigianPhântíchgiảithuật(AnalyzingofAlgorithm)làquátrìnhtìmranhữngđánhgiávềtàinguyêncầnthiếtđểthựchiệngiảithuậtĐỘPHỨCTẠPTHUẬTTOÁNĐộphứctạpvềthờigiancủagiảithuật:•Đượcquivềđếmsốlệnhcầnthựcthicủagiảithuật•ĐólàmộthàmT(n)phụthuộcvàokíchthướcncủainput•Coinhưcómộtmáytrừutượng(abstractmachine)đểthựchiệngiảithuậtĐỘPHỨCTẠPTHUẬTTOÁN•Thờigiantốithiểuđểthựchiệngiảithuậtvớikíchthướcđầuvàongọilàthờigianchạytốtnhất(bestcase)củagiảithuật•Thờigiannhiềunhấtđểthựchiệngiảithuậtvớikíchthướcđầuvàonđượcgọilàthờigianchạyxấunhất(worstcase)củagiảithuật•Thờigiantrungbìnhđểthựchiệngiảithuậtvớikíchthướcđầuvàonđượcgọilàthờigianchạytrungbình(averagecase)củagiảithuậtVídụĐánhgiáđộphứctạpvềthờigiancủagiảithuậtSearch(x,a,n)fori1ton doifai=x thenreturntruereturnfalse dssdsdsssssssssssslkcddkcf;dxkacBIỂUDIỄNTHỜIGIANCHẠYBỞIKÝHIỆUOGiảsửf(n)vàg(n)làhàmthựckhôngâmcủađốisốnguyêndươngn, tanóif(n)=O(g(n))nếucóhằngsốc>0vàsốnguyêndươngNsaochof(n)=NNếugiảithuậtcóthờigianchạytốtnhất(trungbình,xấunhất)làT(n)vàT(n)=O(g(n))thìtanóiđộphứctạpcủagiảithuậttrongtrườnghợptốtnhất(trungbình,xấunhất)làO(g(n))Vídụ:Giảsửf(n)=5n3+2n2+13n+6,tacó:f(n)=5n3+2n2+13n+6=1)f(n)=O(n3)Tổngquátnếuf(n)làmộtđathứcbậckcủan:f(n)=aknk+ak1nk1+...+a1n+a0thìf(n)=O(nk)QuyTắc QUYTẮCCỘNG:NếuđoạnchươngtrìnhP1 cóthờigianthựchiệnT1(n)=O(f(n))vàđoạn chươngtrìnhP2cóthờigianthựchiệnlà T2(n)=O(g(n))thìthờigianthựchiệnP1rồi đếnP2tiếptheosẽlà:T1(n)+T2(n)=O(f(n) +g(n)) QUYTẮCNHÂN:NếuđoạnchươngtrìnhP cóthờigianthựchiệnlàT(n)=O(f(n)).Khi đó,nếuthựchiệnk(n)lầnđoạnchươngtrình Pvớik(n)=O(g(n))thìđộphứctạptínhtoán sẽlàO(g(n).f(n)) QUYTẮCMAX:NếuđoạnchươngtrìnhPcó thờigianthựchiệnT(n)=O(f(n)+g(n))thìcó thểcoiđoạnchươngtrìnhđócóđộphứctạpĐộphứctạp(tăngdần)•O(1)Hằngsố•O(log2n)Logarithm•O(n)Tuyếntính•O(nlog2n)nlogn•O(n2)Bậchai•O(n3)Bậcba•O(nm)Đathức•O(mn),m>=2Hàmmũ•O(n!)GiaithừaVÍDỤ Viếtvàphântíchgiảithuậttínhgiaithừacủa sốtựnhiênn.