O(f(x)) và đánh giá thời gian thực hiện thuật toán

Tài liệu tham khảo về O(f(x)) và đánh giá thời gian thực hiện thuật toán
Nội dung trích xuất từ tài liệu:
O(f(x)) và đánh giá thời gian thực hiện thuật toánO(f(x))vàđánhgiáthờigianthựchiệnthuật toán.Khiđánhgiáthờigianthựchiệnbằngphươngpháptoánhọc,chúngtasẽbỏquanhântốphụthuộcvàocáchcàiđặtchỉtậptrungvàoxácđịnhđộlớncủathờigianthựchiệnT(n).Giảsửnlàsốnguyênkhôngâm.T(n)vàf(n)làcáchàmthựckhôngâm.TaviếtT(n)=O(f(n))(đọcT(n)làôlớncủaf(n)),nếuvàchỉnếutồntạicáchằngsốdươngcvànosaochoT(n)≤c.f(n),vớimọin≥no.NếumộtthuậttoáncóthờigianthựchiệnT(n)=O(f(n)),tanóithuậttoáncóthờigianthựchiệncấpf(n).Từđịnhnghĩakýhiệuôlớn,tacóthểxemrằnghàmf(n)làcậntrêncủaT(n).Vídụ.GiảsửT(n)=3n2+4n+5.Tacó3n2+4n+5≤3n2+4n2+5n2=12n2,vớimọin≥1.VậyT(n)=O(n2).Trongtrườnghợpnàytanóithuậttoáncóthờigianthựchiệncấpn2,hoặcgọnhơn,thuậttoáncóthờigianthựchiệnbìnhphương.Dễdàngthấyđược,nếuT(n)=O(f(n))vàf(n)=O(f1(n)),thìT(n)=O(f1(n)).Thậtvậy,vìT(n)làôlớncủaf(n)vàf(n)làôlớncủaf1(n)nêntồntạicáchằngsốco,no,c1,n1saochoT(n)≤c0f(n)vớimọin≥n0vàf(n)≤c1f1(n)vớimọin≥n1.TừđótacóT(n)≤c0c1f1(n)vớimọin≥max(n0,n1).Khibiểudiễncấpcủathờigíanthựchiệnthuậttoánbởihàmf(n),chúngtasẽchọnf(n)làhàmnhỏnhất,đơngiảnnhấtcóthểđượcsaochoT(n)=0(f(n)).Thôngthườngf(n)làcáchàmsốsauđây:f(n)=1;f(n)=logn;f(n)=n;f(n)=nlog(n);f(n)=n2;n3…;f(n)=2n.NếuT(n)=O(1)điềunàycónghĩalàthờigianthựchiệnthuậttoánđượcchặntrênbởimộthằngnàođó,trongtrườnghợpnàytanóithuậttoáncóthờigianthựchiệnhằng.NếuT(n)=O(n),tứclàbắtđầutừmộtn0nàođótrởđitacóT(n)≤cnvớimộthằngsốcnàođó,trongtrườnghợpnàytanóithuậttoáncóthờigianthựchiệntuyếntính.Bảngsauđâychotacáccấpthờigianthựchiệnthuậttoánđượcsửdụngrộngrãinhấtvàtêngọicủachúng. Hình 1Danhsáchtrênsắpxếptheothứtựtăngdầncủahàmthờigianthựchiện.Cáchàmloại:2n,n!,nnthườngđượcgọilàcáchàmloạimũ.ThuậttoánvớithờigianchạycócấphàmloạimũthìtốcđộrấtchậmCáchàmn,n3,n2,nlog2nthườngđượcgọilàcáchàmđathức.Thuậttoánvớithờigianchạycócấphàmđathứcthườngchấpnhậnđược