Page 25 - โครงสร้างข้อมูลและขั้นตอนวิธี
P. 25
การวัดประสิทธิภาพและความซับซ้อนของขั้นตอนวิธี 2-15
เรอื่ งท่ี 2.1.2
การเตบิ โตข องการร วมกันของฟังก์ชนั
การหาการเติบโตของฟังก์ชันด้วยบ๊ิกโอของฟังก์ชันท่ีมีความซับซ้อนท่ีเกิดจากการรวมกันของฟังก์ชันต้ังแต่
2 ฟังก์ชันข้ึนไป สามารถท�ำได้โดยการแยกหาบิ๊กโอของแต่ละฟังก์ชันก่อน แล้วจึงน�ำบ ๊ิกโอท่ีได้มาพิจารณาร่วมกัน
การพิจารณาร่วมกันน้ีอาจเป็นได้ทั้งการบวกฟังก์ชันท้ังสองเข้าด้วยกัน หรือการคูณฟังก์ชันท้ังสอง การรวมกันของ
ฟังก์ชันเช่นนี้ส อดคล้องกับการท�ำงานของข้ันตอนวิธีท่ีในบางครั้งขั้นตอนวิธีอาจเกิดจากการรวมหลายข้ันตอนวิธีหรือ
การประมวลผลย่อยเข้าด้วยกัน จ�ำนวนข้ันตอนการท�ำงานและเวลาที่ใช้ในการแก้ปัญหาจึงเป็นการรวมการประมวล
ผลและเวลาท่ีใช้ในก ารประมวลผลย่อยต่างๆ เหล่านั้น ดังนั้น รูปแบบการหาบ ๊ิกโอข องการรวมกันของฟังก์ชันที่เป็นไป
ได้มีดังต่อไปน้ี
1. การบวกก นั ของฟ งั ก์ชัน
การร วมกันของฟ ังก์ชันด ้วยก ารบวก
เเดมชัง่นื่อนพ้ันf1ิจ(จาxระ)ณไ=ดา้xถh2ึง(xกแ)ลาร=ะห ffา21บ((xx๊ิก))โ=+อข4fอ2x(งxแh)ล=(xะ)ใxหจ2ะ้ +hได(4x้วx)่าเปh(็นxก) า=รOบ ว(xก2ส)อตงาฟมัทงกฤ์ชษันฎนีบ้ีเทข้าพดห้วุนยากมันแต่เนื่องจาก h(x) สามารถ
ฟแOยัง(xกก2์ชเ)ปันซ็นึ่ง2กเาฟทร่าังพกกิจับ์ชาันขรอใณดบาๆเกขาสตราบบมนวากรทถก่ีใพันหิจขญาอ่ทรงณ่ีสfุ1ดาไรกดะับ้ดหfังว2น่าไงี้ ดf้1ซก่ึงับf1f(2x)ค=ือOO((xx22))แนลั่นะเอf2ง(xด)ัง=น้ันO(กxา)รจหะาเหบ็น๊ิกวโอ่าจบา๊ิกกโกอาขรอบงวhก(กxัน) ขเปอ็นง
ตัวยืนยันสแป |ค(fลมรว1ะะมา+มมตcาส2fิใณ2ัมหก)ค(พ้ับxf่าัน1)ผ|x||(ธffx2 ล21์ )(≤=fรเx(1ปเxว()ป x|็น)ม|||็น)≤ffตข≤11=อัว((OcxxยงcO2))(ฟ1ืน||g(g+|ังg+gย12ก(11ัน(fx|(x2์(ชfxคx)(2)ัน)x)|)(ว)x)แเาเf|จม)ม1มล|(ะื่อ่ือxสะโได)ัดมxxfยแ2้พว>(ล>ส่าxันะม)xธxบfเ2์12ปfัต2(็นx(ิอx)ส)Oจม=ะ(กgไOด2าร((้xgอ)2ิง)(รจxูป)า)สกจาบมะทไเดหน้วลิย่า่ียามม 2.1 บ๊ิกโอ จะได้ว่ามี c1 กับ x1 เป็น
|a + b| ≤ |a| + |b|
||เก(( มff�ำ11ื่อห++นxดffม22))gีค((xx(่าx))ม||)า ก=≤≤≤≤กว m||(c่าffc|11ทg1a((xxั้ง(x+x))(x||)|cg|1++21แ)(|||ffxลg22)ะ(((|xxx,x)))||||2g≤≤จ2(ะccxไ11)ด|||gg้แ1(xล(x)ะ|)|+c+=cc2c|2g|1g(x+2()x|c)2| จะได้
ซึ่งสอดคลเพ้อรงากะับฉบะทนนั้นิย |า(fม1บ+๊ิกโf2อ)(ดx)ัง|น≤ั้นcส|gาม(xา)ร|ถเมส ื่อรุปxเป>็นxท0ฤโษดฎยีบทที่ xไ0ด=้ ดmังนa้ี x(x1, x2) และ c = c1 + c2 เป็นตัวยืนยัน
