Performance Analysis

บทที่ 2 การวิเคราะห์ ประสิทธิภาพของอลั กอริทึม(Performance Analysis) 1

บทท่ี 2 การวเิ คราะห์ ประสทิ ธภิ าพของอลั กอรทิ มึ • คณติ ศาสตรพ์ น้ื ฐานสาหรบั การวเิ คราะหป์ ระสทิ ธภิ าพของ อลั กอรทิ มึ อะไร • การวดั ประสทิ ธภิ าพอลั กอรทิ มึ • อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates) • เปรยี บเทยี บอตั ราการเตบิ โตของอลั กอรทิ มึ • การนบั ตวั ดาเนนิ การ (Operation Counts) • ฟงั กช์ นั อตั ราการเตบิ โตตามการวดั ประสทิ ธภิ าพของอลั กอรทิ มึ • การวเิ คราะห์ Best-case, Worst-case และ Average-case • สรปุ เน้อื หาบทท่ี 2 2

คณิตศาสตรพ์ น้ื ฐานสาหรบั การวเิ คราะหป์ ระสทิ ธภิ าพของอลั กอรทิ มึลอการิทึม (Logarithms)การจดั การขอ้ มลู ในหน่วยความจาหรอื ในดสิ กใ์ หม้ คี วามสมั พนั ธล์ อการทิ มึ ของคา่ y ฐาน bจะเขยี นอยใู่ นรปู ลอการทิ มึ ได้ คอื ������������������������ ������ = ������ ดงั นนั้ ถา้ log������ ������ = ������ แลว้ ������������ = ������ และ blogb y = y ตวั อยา่ งเชน่ log2 1000 = 10 หาไดจ้ าก 210=1000คุณสมบตั ขิ องลอการทิ มึ มดี งั น้ี1. log ������������ = log ������ + log ������2. log ������/������ = log ������ − log ������3. log ������������ = ������ log ������ log������ ������4. log������ ������ = log������ ������ 3

คณิตศาสตรพ์ น้ื ฐานสาหรบั การวเิ คราะหป์ ระสทิ ธภิ าพของอลั กอรทิ มึผลรวม (Summation)การบวกตวั เลขทอ่ี ยใู่ นชว่ งของกลมุ่ ขอ้ มลู โดยใชส้ ญั ลกั ษณ์ ซกิ มา ( : Sigma)������������=1 ������ ������ = ������ 1 + ������ 2 + ⋯ + ������ ������ − 1 + ������(������)เลขยกกาลงั (Logarithm)• การบวกเลขยกกาลงั n2+3n+n2+n+1 = (n2+n2)+(3n+n)+1 = 2n2+4n+1• การคณู เลขยกกาลงั n*(n+1) = n2+n 4

การวดั ประสทิ ธภิ าพอลั กอรทิ มึ • วตั ถุประสงคแ์ รกในการพฒั นาโปรแกรม - พฒั นาขน้ึ มาตอ้ งทางานถกู ตอ้ งและไดผ้ ลลพั ธต์ ามตอ้ งการ • สง่ิ ทต่ี อ้ งพจิ ารณาหลงั พฒั นาโปรแกรม - ใชเ้ วลาในการประมวลผลนานเกนิ ไปหรอื ไม่ - ใชห้ น่วยความจามากเกนิ ความจาเป็นหรอื ไม่ • เครอ่ื งมอื ทใ่ี ชใ้ นการวดั ประสทิ ธภิ าพอลั กอรทิ มึ - การวเิ คราะหห์ น่วยความจาทใ่ี ชใ้ นการประมวลผล (Space Complexity Analysis) - การวเิ คราะหเ์ วลาทใ่ี ชใ้ นการประมวลผล (Time Complexity Analysis) 5

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหห์ น่วยความจาที่ใช้ในการประมวลผล(Space Complexity Analysis) • การวเิ คราะหห์ น่วยความจาทงั้ หมดทโ่ี ปรแกรมใชใ้ นการประมวลผลของอลั กอรทิ มึ • เพอ่ื ใหท้ ราบถงึ ขนาดขอ้ มลู ทส่ี ามารถป้อนหรอื สง่ ขอ้ มลู เขา้ มาใหอ้ ลั กอรทิ มึ ประมวลผล แลว้ ไมเ่ กดิ ขอ้ ผดิ พลาด 6

การวดั ประสทิ ธภิ าพอลั กอรทิ มึ 7การวิเคราะหห์ น่วยความจาท่ีใช้ในการประมวลผล(Space Complexity Analysis)  องคป์ ระกอบของการวิเคราะหห์ น่วยความจาท่ีใช้ในการประมวล • Instruction Space คอื ขนาดหน่วยความจาทจ่ี าเป็นตอ้ งใชข้ ณะคอมไพเลอร์ (Compiler) โปรแกรม • Data Space คอื ขนาดหน่วยความจาทจ่ี าเป็นตอ้ งใชส้ าหรบั เกบ็ ขอ้ มลู ค่าคงท่ี และตวั แปรทใ่ี ชใ้ นขณะประมวลผลโปรแกรม ซง่ึ แยกออกได้ 2 ประเภท คอื o Static memory ขนาดหน่วยความจาทต่ี อ้ งใชใ้ นการประมวลผลอยา่ ง แน่นอน เชน่ หน่วยความจาทใ่ี ชเ้ กบ็ คา่ คงท่ี หรอื ตวั แปรชนดิ อารเ์ รย์ o Dynamic memory ขนาดหน่วยความจาทต่ี อ้ งใชใ้ นการประมวลผลทไ่ี ม่ แน่นอน คอื จะรวู้ า่ ตอ้ งใชห้ น่วยความจาเทา่ ไรกต็ ่อเมอ่ื โปรแกรมตอ้ งใชง้ าน นนั้ เอง เชน่ การประกาศตวั แปรพอยเตอร์ (Pointer) ในภาษา C หรอื การ เกบ็ ขอ้ มูลในรปู แบบลงิ คล์ สิ ตท์ ส่ี ามารถเพมิ่ หรอื ลดขนาดการเก็บขอ้ มูลได้ แบบอตั โนมตั โิ ดยไมต่ อ้ งจองพน้ื ทห่ี น่วยความจาไวก้ ่อนใชง้ าน

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหห์ น่วยความจาที่ใช้ในการประมวลผล(Space Complexity Analysis)  องคป์ ระกอบของการวิเคราะหห์ น่วยความจาที่ใช้ในการประมวล • Environment Stack Space คอื หน่วยความจาทใ่ี ชส้ าหรบั เกบ็ ขอ้ มลู ผลลพั ธท์ ่ี ได้จากการประมวลผล เพ่ือรอเวลาท่ีจะนากลับไปใช้ใหม่ในโปรแกรม ซ่ึง หน่วยความจาประเภทน้ีจะเกดิ ขน้ึ เมอ่ื มกี ารใชง้ านเทา่ นนั้ 8

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหห์ น่วยความจาที่ใช้ในการประมวลผล(Space Complexity Analysis) ตวั อย่างท่ี 2.1 วเิ คราะหห์ น่วยความจาทใ่ี ชใ้ นการประมวลผลของโคด้ ต่อไปน้ี 1 +SpaceAnalysis(in data1:int,in data2:int):int 2 int temp 3 temp = data1 + data2 4 return temp • ประกาศตวั แปรทงั้ หมด 3 ตวั แปร คอื data1, data2 และ temp • ทงั้ สามตวั แปรมชี นดิ ขอ้ มลู คอื integer (ภาษา Java ขนาด 4 ไบต,์ ภาษา C ขนาด 2 ไบต)์ • ใชพ้ น้ื ทห่ี น่วยความจา 3*4 = 12 ไบต์ (ภาษา C ใชห้ น่วยความจา 3*2 = 6 ไบต)์ 9

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหห์ น่วยความจาที่ใช้ในการประมวลผล(Space Complexity Analysis) ตวั อย่างที่ 2.2 วเิ คราะหห์ น่วยความจาทใ่ี ชใ้ นการประมวลผลของโปรแกรมแบบวนซ้า 1 +Factorial(in n:int):int 2 if (n == 0) 3 return 1 4 else return n * (Factorial(n-1)) • พจิ ารณาตามจานวนรอบทว่ี นซ้า ถา้ กาหนดให้ n มคี า่ เทา่ กบั 3 จะตอ้ งทาการวนซ้า 3 ครงั้ • ใชพ้ น้ื ทใ่ี นหน่วยความจา เทา่ กบั 3 * 4 = 12 ไบต์ (ภาษจาวา) • สรปุ ไดว้ า่ ถา้ กาหนดใหห้ าคา่ แฟคทอเรยี ล n จะตอ้ งใชพ้ น้ื ทห่ี น่วยความจาเทา่ กบั n * 4 ไบต์ (ภาษา Java ) ในการคานวณหาคา่ แฟคทอเรยี ล n 10

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหเ์ วลาที่ใช้ในการประมวลผล (Time Complexity Analysis)• การวเิ คราะหข์ นั้ ตอนของการดาเนินการทต่ี อ้ งใชใ้ นการประมวลผลของอลั กอรทิ มึ• เพอ่ื ใชป้ ระมาณการเวลาทใ่ี ชป้ ระมวลผล• ทราบถงึ ประสทิ ธภิ าพการทางานของโปรแกรมและแกไ้ ขปญั หาไดอ้ ยา่ งถกู ตอ้ ง• สามารถนาไปใชเ้ ลอื กเครอ่ื งคอมพวิ เตอรท์ เ่ี หมาะสมกบั การประมวลผลของอลั กอรทิ มึ หลกั การพิจารณาเวลาท่ีใช้ประมวลผล • เมอ่ื ประมวลผลโปรแกรมในเครอ่ื งคอมพวิ เตอรท์ ม่ี ปี ระสทิ ธภิ าพเรว็ กวา่ กจ็ ะประมวลผล ขอ้ มลู ไดเ้ รว็ กวา่ • เมอ่ื รนั โปรแกรมทม่ี ผี ลการทางานเดยี วกนั โปรแกรมทม่ี โี คด้ น้อยกวา่ จะทางานไดเ้ รว็ กวา่ • ตวั แปรทม่ี ขี นาดหน่วยความจาเลก็ วา่ จะประมวลผลไดเ้ รว็ กวา่ 11

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหเ์ วลาท่ีใช้ในการประมวลผล (Time Complexity Analysis) ประเภทของเวลาท่ีใช้ในการประมวลผล • Compile time เป็นเวลาทใ่ี ชใ้ นการตรวจไวยากรณ์ (Syntax) • Run time หรือ Execution time เป็นเวลาทเ่ี ครอ่ื งคอมพวิ เตอรใ์ ชใ้ นการประมวลผล อลั กอรทิ มึ ซง่ึ ขน้ึ อยกู่ บั ชนิดขอ้ มลู , จานวนตวั แปรทใ่ี ชใ้ นโปรแกรม และจานวนลปู 12

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหเ์ วลาที่ใช้ในการประมวลผล (Time Complexity Analysis)ตวั อย่างที่ 2.3 วเิ คราะหเ์ วลาทใ่ี ชใ้ นการประมวลผลของโคด้ ต่อไปน้ี1 int n = 20;  กาหนดคา่ 1 ครงั้2 int total = 0;  กาหนดคา่ 1 ครงั้3 while(n != 20){  เปรยี บเทยี บ n+1 ครงั้4 total += n;  คานวณ n ครงั้5 ++n;  คานวณ n ครงั้6 } //end while  แสดงผล 1 ครงั้7 System.out.println(“ผลรวม = ” + total);กาหนดให้ f(n) แทนประสทิ ธภิ าพในการวเิ คราะหเ์ วลาทใ่ี ชใ้ นการประมวลผล n แทนจานวนรอบในการทางานจะไดว้ า่ อลั กอรทิ มึ น้ีมปี ระสทิ ธภิ าพ f(n) = 1 + 1 + (n + 1) + n + n + 1 = 3 n +4 13

การวดั ประสทิ ธภิ าพอลั กอรทิ มึการวิเคราะหเ์ วลาท่ีใช้ในการประมวลผล (Time Complexity Analysis)ตวั อย่างท่ี 2.4 วเิ คราะหเ์ วลาทใ่ี ชใ้ นการประมวลผลของโปรแกรมแบบวนซ้า1 +Factorial(in n:int):int  ถกู เรยี กใช้ n ครงั้2 if (n == 0)  ตรวจสอบเงอ่ื นไข n ครงั้3 return 1  คนื คา่ 1 ครงั้4 else return n * (Factorial(n-1))  เรยี กใชต้ วั เอง n ครงั้f(n) = n + n + 1 + n = 3n +1 14

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)• เครอ่ื งมอื ในการวดั ประสทิ ธภิ าพของอลั กอรทิ มึ เชน่ Big-O, Big-Omega, Big-Teta, Little-o และ Little-omgaอตั ราการเติบโต Big-O • เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาทใ่ี ชใ้ นการประมวลผลของอลั กอรทิ มึ • เป็นฟงั กช์ นั เวลาขอบเขตบนทใ่ี ชใ้ นการประมวลผล (Asymptotic upper bounds) • สญั ลกั ษณ์เป็นตวั โอใหญ่ (O) • O(n) หมายถงึ ฟงั กช์ นั น้ีจะใชเ้ วลาในการประมวลผลน้อยกวา่ หรอื เทา่ กบั n (<n) เสมอ 15

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-O นิยาม Big-O ฟงั กช์ นั f(n) = O(g(n)) กต็ อ่ เมอ่ื มคี า่ คงท่ี m,c ทท่ี าให้ f(n) < cg(n) เมอ่ื n > m 16

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Oตวั อย่างที่ 2.5 กาหนดให้ f(n) = 5n4 – 37n3 + 13n – 4 สามารถแสดงการหาคา่ Big-O และ คา่ คงท่ี c กบั m ไดด้ งั น้ี จาก f(n) = |5n4-37n3+13n–4| < c|n4| โดยท่ี n > m จะไดว้ า่ เมอ่ื กาหนดให้ m = 1 จะทาให้ n > 1 สามารถทาใหก้ ารดาเนินการถกู ตอ้ งไดด้ งั น้ี |5n4-37n3+13n–4| < |5n4+37n4+13n4+ 4n4| (เน่ืองจาก 37n4 > 37n3) < 59|n4| เพราะฉะนนั้ |5n4-37n3+13n–4| < 59|n4| เมอ่ื n > 1 ดงั นนั้ f(n) = 5n4 – 37n3 + 13n – 4 ∈ O(n4) จงึ ไดว้ า่ c = 59, n = 1 และ Big-O คอื O(n4)Noteสรปุ แนวคดิ การหา Big-O จะพจิ ารณาคา่ ทม่ี ผี ลกระทบมากทส่ี ดุ เพยี งคา่ เดยี ว ซ่งึ คา่ คงท่ี cมผี ลน้อยกวา่ คา่ ทม่ี ผี ลกระทบมากทส่ี ดุ ดงั นนั้ จงึ นาคา่ ทม่ี ผี ลกระทบมากทส่ี ดุ เป็นคา่ ของตวัวดั ประสทิ ธภิ าพของ Big-O 17

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Omega () • เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาทใ่ี ชใ้ นการประมวลผลของอลั กอรทิ มึ • เป็นฟงั กช์ นั เวลาขอบเขตลา่ งทใ่ี ชใ้ นการประมวลผล (Asymptotic lower bounds) • สญั ลกั ษณ์เป็นตวั โอเมกา้ ใหญ่ (  ) •  (n) หมายถงึ ฟงั กช์ นั น้ีจะใชเ้ วลาในการประมวลผลมากกวา่ หรอื เทา่ กบั n (> n) เสมอ 18

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Omega () นิยาม Big-Omega ฟงั กช์ นั f(n) = (g(n)) กต็ ่อเมอ่ื มคี า่ คงท่ี m,c ทท่ี าให้ f(n) > cg(n) เมอ่ื n > m 19

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Omega ()ตวั อย่างที่ 2.6 กาหนดให้ f(n) = 5n4 – 37n3 + 13n – 4 สามารถแสดงการหาคา่ Big-  และคค่ งท่ี c กบั m ไดด้ งั น้ี จาก f(n) = |5n4-37n3+13n–4| > c|n| โดยท่ี n < m จะไดว้ า่ เมอ่ื กาหนดให้ m = 1 จะทาให้ n > 1 สามารถทาใหก้ ารดาเนนิ การถูกตอ้ งไดด้ งั น้ี |5n4-37n3+13n–4| > |5n+37n+13n+4n| > 59|n| เพราะฉะนนั้ |5n4-37n3+13n–4| > 59|n| เมอ่ื n > 1 จงึ ไดว้ า่ c = 59, n = 1 และ Big-  คอื  (n) Note สรุปแนวคดิ การหา Big- จะพจิ ารณาคา่ ทม่ี ผี ลกระทบน้อยทส่ี ุดเพยี งค่าเดยี ว ซ่ึงคา่ คงท่ี c มี ผลมากกว่าค่าทม่ี ผี ลกระทบน้อยทส่ี ุด ดงั นัน้ จงึ นาค่าทม่ี ผี ลกระทบน้อยท่ีสุดเป็นค่าของตวั วดั ประสทิ ธภิ าพของ Big-  20

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Theta ()• เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาทใ่ี ชใ้ นการประมวลผลของอลั กอรทิ มึ• เป็นฟงั กช์ นั เวลาขอบเขตบนและขอบเขตลา่ งทใ่ี ชใ้ นการประมวลผล (Asymptotic lower bounds)• สญั ลกั ษณ์เป็นตวั เทตา้ ใหญ่ ( )• (n) หมายถงึ ฟงั กช์ นั น้ีจะใชเ้ วลาในการประมวลผลระหวา่ ง Big- และ Big-O เสมอ 21

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Theta ()นิยาม Big- Thetaฟงั กช์ นั f(nโ)ด=ยทฟ่ี (gงั ก(nช์ ))นั กcต็ 1g่อ(เnม)อ่ื คมอืคี ขา่ อคบงทเข่ี cต1ด, า้cน2 ลแา่ลงะm(ทg(ท่ี nา))ให้ c1g(n) < f(n) < c2g(n) เมอ่ื n > m c2g(n) คอื ขอบเขตดา้ นบน O(g(n)) 22

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Big-Theta ()ตวั อย่างท่ี 2.7 กาหนดให้ f(n) = 5n4 – 37n3 + 13n – 4 สามารถแสดงการหาคา่ Big-  และคา่ คงท่ี c1, c2 กบั m ไดด้ งั น้ี < c|n4| โดยท่ี n < m จะไดว้ ่า จาก f(n) = c|n| < |5n4-37n3+13n–4|เมอ่ื กาหนดให้ m = 1 จะทาให้ n > 1 สามารถทาใหก้ ารดาเนินการถกู ตอ้ งไดด้ งั น้ี |5n+37n+13n+4n| < |5n4-37n3+13n–4| < |5n4+37n4+13n4+4n4| 59|n| < |5n4-37n3+13n–4| < 59|n4|เพราะฉะนนั้ 59|n| < |5n4-37n3+13n–4| < 59|n4| เม่อื n > 1จงึ ไดว้ า่ c1 = 59, c2 = 59, n = 1 และ Big-  มคี ่าระหว่าง O(n4),  ( n)Noteสรุปแนวคดิ การหา Big- เป็นการหาผลกระทบทอ่ี ยรู่ ะหว่าง Big-O กบั Big-  โดยพจิ ารณาค่าทม่ี ผี ลกระทบน้อยทส่ี ุดเพยี งค่าเดยี ว ซ่งึ ค่าคงท่ี c1 มผี ลมากกว่าค่าทม่ี ีผลกระทบน้อยทส่ี ดุ และเมอ่ื พจิ ารณาคา่ ทม่ี ผี ลกระทบมากทส่ี ดุ เพยี งคา่ เดยี ว คอื คา่ คงท่ี c2 23

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Little-o • เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาทใ่ี ชใ้ นการประมวลผลของอลั กอรทิ มึ • มขี อบเขตการเวลาทใ่ี ชป้ ระมวลผลคลา้ ยกบั Big-O แตไ่ มแ่ ตะขอบเขตบนของฟงั กช์ นั เวลา • สญั ลกั ษณ์เป็นตวั โอเลก็ (o) • o(n) หมายถงึ ฟงั กช์ นั น้ีจะใชเ้ วลาในการประมวลผลน้อยกวา่ n (< n) เสมอ 24

อตั ราการเตบิ โตของอลั กอรทิ มึ (Algorithm Growth Rates)อตั ราการเติบโต Little-omega • เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาทใ่ี ชใ้ นการประมวลผลของอลั กอรทิ มึ • มขี อบเขตการเวลาทใ่ี ชป้ ระมวลผลคลา้ ยกบั Big-Omega แต่ไมแ่ ตะขอบเขตลา่ งของฟงั กช์ นั เวลา • สญั ลกั ษณ์เป็นตวั โอเมกาเลก็ ( ) •  (n) หมายถงึ ฟงั กช์ นั น้ีจะใชเ้ วลาในการประมวลผลมากกวา่ n (> n) เสมอ 25

เปรยี บเทยี บอตั ราการเตบิ โตของอลั กอรทิ มึ  Big-O (O) มชี ว่ งเวลาทางานทน่ี ้อยกว่าหรอื เทา่ กบั n  Big-Omega (  ) มชี ว่ งเวลาทางานทม่ี ากกว่าหรอื เท่ากบั n  Big-Teta (  ) มชี ว่ งเวลาทางานอย่รู ะหวา่ ง Big-O และ Big-Omega  Little-o (o) มชี ่วงเวลาทางานทน่ี ้อยกว่า n  Little-omega ( ) มชี ่วงเวลาทางานทม่ี ากกวา่ n 26

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบค่าคงท่ี (Constant)ตวั อย่าง 2.8 การนบั ตวั ดาเนินการแบบคา่ คงท่ี1 count = 0; 12 Total = (1+n)*(n/2); 1f(n) = 1+1 = 2 จงึ ไดว้ า่ Big-O = O(2) 27

การนบั ตวั ดาเนินการ (Operation Counts)นับตวั ดาเนินการแบบลปู ลาดบั (Linear loops)ตวั อย่าง 2.9 การนบั ตวั ดาเนินการแบบลปู ลาดบั กาหนดให้ n = 31 Total = 0; 12 for (i = 0; i < n; i++){3 Total = Total+i;  n+14} n ค่า i ตรวจ อบเงอ่ื น ข i < n บรรทดั Total = Total + i 0   1   2   3   4  จานวนครงั ที่ทา 4 3f(n) = 1 + n + 1 + n = 2n + 2 จงึ ไดว้ า่ Big-O = O(n) 28

การนบั ตวั ดาเนินการ (Operation Counts)นับตวั ดาเนินการแบบลปู ลาดบั (Linear loops)ตวั อย่าง 2.10 การนบั ตวั ดาเนินการแบบลปู ลาดบั กาหนดให้ n = 31 Total = 0; 1 n2 for (i = 1; i < n; i++){ n-13 Total = Total+i;4} ค่า i ตรวจ อบเงื่อน ข i < n บรรทดั Total = Total + i 1   2   3   4  จานวนครงั ท่ีทา 3 2f(n) = 1 + n + n - 1 = 2n จงึ ไดว้ า่ Big-O = O(n) 29

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบลปู ลาดบั (Linear loops)ตวั อย่าง 2.11 การนบั ตวั ดาเนินการแบบลปู ลาดบั กาหนดให้ n = 31 Total = 0; 1 n+22 for (i = 0;i <= n; i++){ n+13 Total = Total+i;4}ค่า i ตรวจ อบเงือ่ น ข i < n บรรทดั Total = Total + i0 1 2 3 4 5 จานวนครงั ที่ทา 5 4f(n) = 1 + n + 2 + n + 1 = 2n + 4 จงึ ไดว้ า่ Big-O = O(n) 30

การนบั ตวั ดาเนินการ (Operation Counts)นับตวั ดาเนินการแบบลปู ลาดบั (Linear loops)ตวั อย่าง 2.12 การนบั ตวั ดาเนินการแบบลปู ลาดบั กาหนดให้ n = 41 Total = 0; 12 for (i = 0;i < n; i = i+2){ ���������222��������� + 13…4…5}ค่า i ตรวจ อบเงือ่ น ข i < n บรรทดั ที่ 30  f(n) = 1 B+ig���2���-O+1=+O���2(������2���+) ������ = 3���2��� + 21 ไมพ่ จิ ารณา จงึ ไดว้ า่ 22 3 ไมพ่ จิ ารณา4 5 ไมพ่ จิ ารณา6 จานวนครงั ที่ทา 3 2 31

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบลปู ลอการิทึม (Logarithmic loops) • ค่าตวั แปรทท่ี าหน้าทเ่ี ป็นเง่อื นไขของลูปจะมกี ารเพมิ่ ขน้ึ หรอื ลดลงด้วยการคูณหรอื การหารเป็นอตั ราเท่าตวั ตวั อย่าง 2.13 การนบั ตวั ดาเนินการแบบลปู ลอการทิ มึ1 Total = 0; 1 log2 n + 12 for(i=1;i<10;i=i*2){ log2 n log2 n3…4…5} เพ่ิมขึนด้วยการคณู f(n) = 1 + log2 n + 1 + log2 n + log2 n = 3 log2 n + 2 รอบที่ ค่า i บรรทดั ท่ี 2 บรรทดั ท่ี 3 1 จงึ ไดว้ า่ Big-O = O(log2 n) 2 1  3 2  4 4  5 8  16  จานวนครงั ท่ีทา 54 32

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบลปู ลอการิทึม (Logarithmic loops) ตวั อย่าง 2.14 การนบั ตวั ดาเนินการแบบลปู ลอการทิ มึ1 Total = 0; 1 log2 n + 12 for(i=10;i>0;i=i/2){ log2 n log2 n3…4…5} ลดด้วยการหาร รอบท่ี ค่า i บรรทดั ที่ 2 บรรทดั ท่ี 3 f(n) = 1 + log2 n + 1 + log2 n + log2 n 1 = 3 log2 n + 2 2 10   3 5  จงึ ไดว้ า่ Big-O = O(log2 n) 4 2  5 1  0 จานวนครงั ที่ทา 54 33

การนบั ตวั ดาเนินการ (Operation Counts)นับตวั ดาเนินการแบบลปู ซ้อน (Nested loops)• Quadraticตวั อย่าง 2.15 การนบั ตวั ดาเนินการของลปู ซอ้ นแบบ Quadratic กาหนดให้ n = 21 Total = 0; 12 for (i = 0;i < n; i++){ n+13 for (j = 0; j < n; j++){  n(n + 1) = n2+n4…  n*n = n25…  n*n = n26}7} ค่า i ค่า j เงื่อน ข i < n เง่ือน ข j < n บรรทดั ท่ี 4 f(n) = 1 + n + 1 + n(n+1) + n2 + n2 00 = 3n2 + 2n + 2 01    02    จงึ ไดว้ า่ Big-O = O(n2) 10    11    12    20   จานวนครงั ที่ทา    n+1 = 3 n*(n+1) = 6 n*n = 4 34

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบลปู ซ้อน (Nested loops)• Linear Logarithmiccตวั อย่าง 2.16 การนบั ตวั ดาเนินการของลปู ซอ้ นแบบ Linear Logarithmic กาหนดให้ n = 21 Total = 0; 1 n+12 for (i = 0;i < n; i++){  n(log2 n + 1)3 for (j = 1; j < n; j=j*2){  n*log2 n  n*log2 n4…5…6}7}ค่า i j = j * 2 เงือ่ น ข i < n เงื่อน ข j < n บรรทดั ที่ 401   02   11   12   21   จานวนครงั ท่ีทา 3 = n+1 4 = n*(log2 n+1) 2 = n*log2 nf(n) = 1 + n + 1 + n(log2 n+1) + nlog2 n + nlog2 n = 3nlog2 n+n+2จงึ ไดว้ า่ Big-O = O(nlog2 n) 35

การนบั ตวั ดาเนนิ การ (Operation Counts)นับตวั ดาเนินการแบบลปู ซ้อน (Nested loops)• Dependent Quadraticตวั อย่าง 2.17 การนบั ตวั ดาเนินการของลปู ซอ้ นแบบ Dependent Quadratic กาหนดให้ n = 21 Total = 0; 12 for (i = 0;i < n; i++){ n+1 ������ +13 for(j = 0; j < i; j++){  ������ 2 + 14…  ������ ������ +1  ������ ������ +215… 26}7}ค่า i ค่า j เงอื่ น ข i < n เงอื่ น ข j < i บรรทดั ท่ี 4 f(n) = 1+ n + 1 + n n+1 + 200    + 101   10    +n n+1 n n+111    2 212    n+120    = 3n 2 + 2n + 2จานวนครงั ที่ทา 3 = n+1 5=n n +1 + 1 3=n n +1 จงึ ไดว้ า่ Big-O = O n n+1 2 2 2 36

ฟงั กช์ นั อตั ราการเตบิ โตตามการวดั ประสทิ ธภิ าพของอลั กอรทิ มึf(n) แบบการนับตวั ดาเนินการ ประ ิท ิภาพC คา่ คงท่ี (Constant) เรวท่ี ดlog2 n ฟงั กช์ นั ลอการทิ มึ (Logarithmic loops) ช้าที่ ดn ฟงั กช์ นั เชงิ เสน้ (Linear loops)n log2 n ฟงั กช์ นั ลอการทิ มึ เชงิ เสน้ (Linear Logarithmic)n2 ฟงั กช์ นั กาลงั สอง (Quadratic)n3 ฟงั กช์ นั กาลงั สาม (Cubic)nk ฟงั กช์ นั โพลโี นเมยี ล (Polynamial)2n ฟงั กช์ นั เอก็ โพแนนเซยี ล (Exponential)n! ฟงั กช์ นั แฟคทอเรยี ล (Factorial) 37

ฟงั กช์ นั อตั ราการเตบิ โตตามการวดั ประสทิ ธภิ าพของอลั กอรทิ มึ 38

การวเิ คราะห์ Best-case, Worst-case และ Average-caseBase-case การวเิ คราะหห์ าประสทิ ธภิ าพทด่ี ที ส่ี ุดในการประมวลผลของอลั กอรทิ มึ เช่น การคน้ หาขอ้ มลู ในอารเ์ รย์ แลว้ เจอขอ้ มลู ในการตรวจสอบครงั้ แรกWorst case การวเิ คราะห์หาประสทิ ธภิ าพท่แี ย่ท่สี ุดในการประมวลผลของอลั กอรทิ ึม เช่น การค้นหา ขอ้ มลู ในอารเ์ รย์ แลว้ เจอขอ้ มลู ในการตรวจสอบครงั้ สดุ ทา้ ย เป็นตน้ แสดงวา่ กรณนี ้ีเป็นกรณี ทแ่ี ยท่ ส่ี ดุ เพราะตอ้ งตรวจสอบขอ้ มลู จนถงึ ครงั้ สดุ ทา้ ยจงึ จะพบขอ้ มลู ทต่ี อ้ งการAverage-case การหาคา่ เฉลย่ี ของเวลาทใ่ี ชป้ ระมวลผลของอลั กอรทิ มึ 39

สรปุ เน้อื หาบทท่ี 2 • การวิเคราะห์ประสทิ ธิภาพคือการวเิ คราะห์กรณีโอกาสท่แี ย่ท่สี ุดในการทางานของ โปรแกรมท่ีพฒั นา เพ่อื เป็นการรบั ประกนั ได้ว่าการทางานของโปรแกรมจะไม่เกิด โอกาสทแ่ี ยไ่ ปกวา่ น้ี โดยใชอ้ ตั ราการเตบิ โต Big-O เป็นการวดั ประสทิ ธภิ าพเชงิ เวลาท่ี ใชใ้ นการประมวลผลของอลั กอรทิ มึ • ประสทิ ธภิ าพของอลั กอรทิ มึ จะพจิ ารณาได้จากตวั บ่งช้ี 3 ตวั คอื Best-case, Worst-case และ Average-case 40