ประสิทธิภาพการทำงานของอัลกอริทึม
ประสิธิภาของอัลกอริทึม โดยทั่วไปมีมตรฐานการวัดผลสองแบบโดยแบบแรกคือ การใช้พื้นที่ว่าง (Space Utilization)เป็นจำนวนของหส่วยความจำที่ต้องการใช้เพื่อให้งานสำเร็จประกอบ ด้วยพื้นที่เก็บคำสั่งทา นที่เก็บข้อมูล และพื้นที่สภาวะแวดลอ้มสแตกแบบที่ 2คือประสิทธิภวะเวลา (Time Efficiency) เป็นจำนนของเวลาที่ต้องกรใช้การประมวลผลข้อมูลเพื่อให้งาน สำเร็จ การสำทั้งสองแบบมาวัดปลด้วยันไม่สามารถเป็นไปได้ เนื่องจากอัลกอริทึมที่ขอใหชื้นที่หน่วยความจำได้ต้อ่ยกว่ามักจะทำงานช้า กว่าอัลกอริทึมที่ขอได้มากกว่าดังนั้น ผู้เขียนแรแกรมจึงต้งเลือกว่าจะใช้การขอในที่ว่างหรือประสิทธิภาพเวลา แต่แระสิธิภาพเวลาของอัลกอริทึมจะมีความสำคัญกว่าจึงนำมาใช้พิจารณาซึ่งเวลา ที่ใช้ในการทำงานของอัลกอริทึมชขึ้นกับปัจจัยหลายๆอย่างดังนี้
1.ขนาดข้อมูลที่รับเข้ามาจำ วนของข้อมูลที่รับเข้ามาทำงานจะมีผลกระทบต่อเวลาที่ใช้ทานใจนการปรมวลล ข้อมูลที่รับเข้ามา เช่นเวลาที่ใช้จัดเรียงลำดับข้อมูลของรายการขึ้นกับ จำนวนของข้อมูลที่มีอยู่ในรายการ ( รายละเอียดการจัดเรียงงลำดับอยู่ในบทที่ 11)ดังนั้นเวลาในทำงานTของอัลกอริทึมจะแสดงในรูปแบบฟังก์ชัน T(n)ของข้อมูล ที่รับเข้ามามีขนาด n ค่า
2. ขนิดของเครื่องคอมพิวเตอร์คำ สั่ง (Instruction)และความเร็วของคอมพิวเตอร์มีผลต่อเวลาในการทำงานปัจจัย นี้ขึ้นกับเครื่องคอมิวเตอร์ที่นำมาใช้ซึ่งไม่สามารถคาดคะเนให้ความหมาย เวลา T(n)อยู่ในลักษณะของเวลาที่เป็นจริง(วินาที)แต่จะนับจำนวนของคำสั่งที่ ใช้ในการทำงานโดยประมาณเป็นเวลาT(n )แทน
3.คุณภาะซอรสโค้ดและคอมไพเลอร์เป็น อีกปัจจัยหนค่งที่มีผลต่อเวลาทีใช้ทำงานซึ่งขึ้นกับคุณภาพของซอร์สโคด้ (SourceCode) ที่เขียนการทำงานเป็นอัลกอริทึมและคุณภาพของคอมไพเลอร์ (Compiler)ในการแปลงซอร์สโค้ดไปเป็นโค้ดถกษาเครื่อง(Machine Code ) ในบางภาษาเขียนโปแกรมมีความเหมาะสมกว่าในการเขียนอัลกอริทึมในขณะที่บาง ภาษามีคอมไพเลอร์ที่แปลงงโค้ดได้ดีกว่า ซึ่งหมายความว่าค่า T(n)ไม่สามารถจะทราบได้เมื่อไช้กับการนับจำนวนของคำสั่ง ในการทำงาน(ข้อ 2)
ประสิทธิภาพกับขนาดข้อมูลที่รับเข้ามา
ตัวอย่าง ต่อไปนี้เป็นอัลกอริทคมที่ได้กล่าวมาแลวนารางที่ 8/.1 เป็นการคำนวนหาค่าเฉลี่ยจากการรับค่าเข้ามา n ค่าท่เก็บไว้ในอาร์เรย์และมี การกำหนดหมายเลขบรรทัดให้กับและประโยคเพื่อความสะดวกในการอ้างถึงได้เป็นดัง ในตารางที่ 8.4
ตารางที่ 8.4อัลกอริทึมการคำนวนหาคาเฉลี่ย
| 1.กำหนดค่าเริ่มต้นให้ตัวแปร sum = 02.กำหนดค่าเริ่มต้นให้ตัวแปรดับนี i =03. วนลูป while i<n ให้ทำดังนี้
4. a.นำค่าของอาร์เรย์ X[i]บวกให้กับตัวแปร sum 5.b. เพิ่ค่าให้กับตัแปร I หนึ่งค่า 6.คำนวนหาค่าเฉลี่ย sum/nและส่งคืนกลับ |
ประโยค บรรทัด 1และ2มีการนำงนเยงครั้งเดียวประโยคบรรทัด4 และ 5 ประกอบกันเป็นการทำงานแบบวนลูปมีการทำงาน n ครั้งประโยคบรรทัด3ซึ่งเป็นตัว ควบคุมการทำงานซ้ำมีการทำงานn+1ครั้งเพิ่ม 1 เข้ามาเป็นการตรวจสอบเงื่อนไข ในกรณีที่ตัวแปร iมีค่าไม่น้อยกว่า n หลังจากจบการวนลูปประโยคบรรทัด6 มีการทำงานครั้งเดียวจากการวิเคราะห์ดังกล่าวได้เป็นตารางผลสรุปดังรูป ที่8.2
| ประโยค # | จำนวนการทำงาน |
| 123
4 5 6 |
11n+1
n n 1 |
| ยอดรวม | 3n+4 |
รูปที่ 8.2จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่ 8.2
T(n)=3n+4
เมื่อ จำนานข้อมูลที่รับเข้ามาเพิ่มขึ้นค่าเวลาในการทำงานของT(n)ก็จะเพิ่มมากขึ้น ตามอัตราส่วนของ nและได้ว่า T(n) มีลำดับขาดตามค่าของ nซึ่งกำหนดเป็น สัญลักษณ์เครื่องหมายบิ๊โอ(BigOh notation) ได้เป็นดังนี้
T(n)= O(n)
ในลักษณะทั่วค่าเวลาT(n) ของอัลกอริทึมจะบอกว่ามีลำดับขนาดตามค่าของ f(n) แสดงเป็น
T(n)= O(f(n))
ถ้ามีค่าคงที่ c จะได้ว่า
T(n) ≤c•f(n) สำหรับทุกๆค่าของ n ที่สามารถมีค่าได้สูงสุด
จะ ได้ว่า T(n)ถูกกำหนดขอบเขตช่วงบนด้วยเวลาคงที่ f(n)สำหรับทุกๆ ค่าของnในช่วงใดช่วงหนึ่งและการคำนวนเชิงซ้อน (ComputationalComplexity)ของ อัลกอริทึมเรียกเป็นO(f(n)) จากลักษณะเชิงซ้อนของอัลกอริทคมตัวอย่างที่ผ่าน มาได้เป็น O(n)โดยพบว่าเวลาที่ใช้ในการทำงานได้เป็น
T(n)=3n+4
และ
3n+4 ≤3n+nสำหรับn≤4
จะได้ว่า
T(n) ≤ 4n สำหรับทุก n ≥ 4
ดังนั้นเมื่อให้ f(n)=nและc=4ก็เขียนได้เป็น
T(n)=O(n)
นอก จากนี้ยังคงมีความถูกต้องเช่นกันเมื่อเขียนเป็น T(n)=O(5280n) หรือ T(n)=O(4n+5)หรือT(n)=O(3.141n+2.71828)แต่การเขียนที่ต้องการจะให้ อยู่ในรูปแบบของฟังก์ชันเรียบง่าย เช่น n , n2หรือlog2เพื่อแสดงให้ทราบถึงลักษณะเชิงซ้อนของอัลกอริทึม และมีรูปแบบทั่วไปเป็น T(n)= O(g(n)) ถ้า g(n) ≥ n สำหรับทุก ๆค่าของ n
ประสิทธิภาพกับการจัดเก็บข้อมูล
จาก ตัวอย่างที่ผ่านมาเวลาที่ใช้ทำงานจะขึ้นกับขนาดหรือจำนวนของข้อมูลที่รับ เข้ามาในปัญหาอื่นๆอาจขึ้นกับวิธีจัดการกับข้อมูลที่รับเข้ามา เช่นการจดเรียงลำดั่บข้อมูลจะใช้เวลาต้องใช้เวลาจัดเรียงลำดับมากขึ้น
ดัง นั้นในการพยายามวัดผลเวลาของ Tอาจใช้ในกรณีดีที่สุด (Best Case)ในกรณีเฉลี่ย (Aver age Case )หรือในกรณีแย่ที่สุด(Worst Cast)การวัดสิทธิภาพของอัลกอริทึมในกรณีดีที่สุดดูเป็นเรื่องง่ายแต่ไม่ สามารถนำมาวัดผลได้และในกรณีเฉลี่ยก็เป็นการยากที่จะต้องพิจารณาค่าเฉลี่ย ที่ชัดเจนแต่ในกรณีที่แย่ที่สุดเหมือนไม่ง่ายแต่ก็ไม่ยากที่จะนำมาใช้วัดผล ดังนั้นเวลาT(n)จึงนำมาใช้วัดประสิทธิภาพของอัลกอริทึมในกรณีที่แย่ที่สุด
ตัวอย่างที่นำมาแสดงเป็นอัลกอริทึมการจัดเรียงลำดับข้อมูลแบบเลือก Selection Sorting)
ดังในตารางที่ 8.5 และมีการกำหนดหมายเลขบรรทัดให้กับแต่ละประโยค
ตารางที่ 8.5 อัลกอริทึมการเรียงลำดับแบบเลือก
| 1.วนลูปforตั้งแต่ i=0ถึงn-2ให้ทำดังนี้2.a กำหนดตัวแปร smallpos มีค่าเท่ากับ i3.b กำหนดตัวแปรsmallestมีค่าเท่ากับอาร์เรย์ X[smallpos]
4.cวนลูป forตั้งแต่ j=i=+1ถึงn-1ให้ทำงานดังนี้ 5.ถ้า X[j]นอ้ยกว่าsmallest ทำดังนี้ 6.1กำหนดตัวแปร smallpos มีค่าเท่ากับ j 7.2กำหนดตัวแปรsmallestมีค่าเท่ากับอาร์เรย์ X[smallpos] 8.dกำหนดอาร์เรย์ X[smallest]มีค่าเท่ากับ X[i] 9.eกำหนดอาร์เรย์X[i] มีค่าเท่ากับ smallest |
ประโยค บรรทัดที่ 1 มีการทำงานบนวนลูป n ครั้งจากช่วงi=0 ถึง n-2 และหนึ่งครั้งเพื่อจบการวนลูป ประโยคบรรทัด2,3,8และ 9 แต่ละบรรทัดมีการทำงาน n-1 ครั้งภายในลูปในการวนลูปรอบแรกค่า i =0 โดยประโยคบรรทัดที่ 4 เป็นตัวควบคุมการทำงานซ้ำมีการทำงาน n ครั้งประโยคบลรรทัด 5 เป็นการตรวจเงื่อนไข มีการทำงาน n-1 และในการทำงานของประโยคบรรทัด 6,7เป็นกรณียี่สุดจึงมีการทำงาน n-1ครั้งเช่นกัน
ในการวนลูปรอบที่ สองค่า I =1 ประโยคบรรทัด4มีการทำงาน n-1 ครั้ง ประโยคบรรทัด 5,6และ7 มีการทำงานทั้งหมดn-2ครั้งเมื่อการทำงานไปเรื่อยๆจนจบจะได้ว่าประโยคบรรทัด 4มีการทำงานทั้งหมด n+(n-1)+…+2 ครั้ง ประโยคบรรทัด 5,6และ7 แต่ละบรรทัดมีการทำงานทั้งหมด(n-1)+ n-2)+…+1ครั้งได้ผลรวมทั้งหมดเท่ากับn(n-1)/2-1 และ n(n-1)/2 ตามลำดับซึ่ง จะได้เวลาในการทำงานของอัลกอริทึมเป็น ดังนี้
T(n)=3n+4(n-1) +-1+3
=2n2+4n-5
เมื่อ n ≤ n2สำหรับทุก n ≥ 0จะได้ว่า
2n2 + 4n – 5 ≤ 2n2 + 4n = 6n2
และได้ว่า
T(n) ≤ 6n2 สำหรับทุกn ≥ 0
กำหนดให้f(n) = n2 และ c = 6 ตามเครื่องหมายบิ๊กโอได้เป็น
T(n) = O(n2)
เครื่อง หมายบิ๊กโอบอกให้ทราบว่าเป็นการวัดผลโดยประมาณกบเวลาการทำงานของอับลกอริทึม สำหรับข้อมูลที่รับเข้ามีจำนวนมาก ๆ ถ้าหากมีสองอัลกอริทึมที่ทำงานกับปัญหาแบบเดียวกันแต่มีลักษณะเชิงซ้อนต่าง กันอัลกอริทึมที่มีเวลาการทำงานน้อยที่สุดจะมีความเวลาการทำงาน T2(n) ของอัลกอริทึม2เป็นO(n2)นะได้ว่าอัลกอริทึม2และมีประสิทธิภาพมากกว่าเมื่อขนาดข้อมูลเท่ากับ n
อย่างไรก็ตาม หากขนาดข้อมูลที่รับเข้ามามีจำนวนน้อยอัลกอริทึม 2อาจดีกว่าอัลกอริทึม 1เช่นไห้ T1(n)=10nและ T2(n)=0.1n2 ซึ่ง 10n<0.1n2 สำหรับค่าของ nที่นอ้ยกว่า 100 และจะได้ว่า
T1(n)< T2(n)สำหรับเฉพาะ n >100
ดังนั้นอัลกอริทึม1มีประสิทธิภาพมากกว่าอัลกอริทึม2 เฉพาะข้อมูลที่รับเข้มีจำนวนมากกว่า100
ประ สิทธิภาพของอัลกอริทึมจึงขึ้นอยู่กับการจัดการกับข้อมูลอย่าไรโดยตัวอย่าง ที่นำมาแสดงให้ทราบความแตกต่างของแต่ละอัลกอริทึมที่ใช้แก้ปัญหาแก้ปัญหาแบบ เดียวซึ่งเป็นการค้นหาค่าที่ต้องการมีอยู่ในอาร์เรย์ที่มีสมาชิกn ตัวหรือ ไม่ แบบแรกเป็นอัลกอริทึมแบบง่าที่นำมาใช้ดำเนินการค้นหาเป็นการค้นหาตามลำดับ เชิงเส้น (Linear Search) ซึ่งเริ่มต้นการค้นหาที่สมาชิกในตำแหน่งแรกของรายการและทดสอบกับ สมาชิกในตำแหน่งถัดแรกของรายการและทดสอบกับสมาชิกในตำแหน่งส่งถัดไปจนกว่าจะ พบค่าที่ต้องการหรือสิ้นสุดการค้นหาที่ท้ายรายการได้เป็นอัลกอริทึมดันใน ตารางที่8.6
ตารางที่ 8.6 อับกอริทึมการค้นหาแบบเชิงเส้น
| 1.การหนดตัวแปร foundมีค่าเท่ากับ false2.กำหนดตัวแปร Ioc มีค่าเท่ากับ 03.วนลูปwhile Ioc ≤ n -1 และnot found ให้ทำดังนี้
4.ถ้า X[Ioc] มีค่าเท่ากับ item ที่ต้องการหาคำดังนี้ 5.กำหนดตัวแปร foundมีค่าเท่ากับTrue 6.ไม่เช่นนั้นเพิ่มหนึ่งค่าให้กับตัวแปร Ioc เท่ากับ Ioc+1 |
ในกรณีแย่ที่สุดของการค้นหาคือไม่พบค่าที่ต้องการมีอยู่ในรายการซึ่งใช้เวลาการทำงาน TL(n)สำหรับอัลกอริทึมการค้นหาแบบเชิงเส้นในรูที่ 8.3
| ประโยค # | จำนวนการทำงาน |
| 123
4 5 6 |
11n+1
n 0 n |
รูปที่ 8.3 จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่8.6
เมื่อ TL(n) = 3n+3 จะได้ว่า
TL(n)=O(n)
และ 3n+3 ≤ 4nสำหรับทุก n ≥ 3
ถ้า หากรายการที่นำมาใช้ค้นหามีการจัดเรียงลำดับข้อมูลอยู่ก่อนแล้วก็สามารถใช้ แบบที่ สองโดยอัลกอริทึมจะดำเนินการค้นหาแบบแบ่งครึ่ง (Binary Search)แทนการใช้แบบเชิงเส้นเป็นการค้นหาที่ต้องการโดยไปยังสมาชิกตรงกลาง ของรายการและทำการตรวจสอบค่าซึ่งมีความเป็นไปได้3 รูปแบบ คือ
1.ค่าที่ต้องการหาน้อยกว่าค่าของสมาชิกที่อยู่ตรงกลาง ค้นหาต่อในส่วนครึ่งแรกที่เหลือของรายการ
2.ค่าที่ต้องการหามากกว่าค่าของสมาชิดที่อยู่ตรงกลางค้นหาต่อในส่ายครึ่งท้ายี่เหลือของรายการ
3.ค่าที่ต้องการหาเท่ากับค่าของสมาลอกที่อยู่ตรงกลางค้นพบค่าที่ต้องการ
กระบวน การค้นหาจะทำไปเรื่อย ๆ จนกว่าจะพบค่าที่ต้องการหรือไม่พบเมือรายการย่อยที่ต้องค้นหาว่างเปล่าได้ เป็นอัลกอริทึมดังในตารางที่8.7
ตารางที่ 8.7 อัลกอริทึมการค้นหาแบบแบ่งครึ่ง
| 1.กำหนดตัวแปร foundมีค่าเท่ากับfalse2.กำหดตัวแปร first มีค่าเท่ากับ 03.กำหดตัวแปร lastมีค่าเท่ากับ n-1
4. วนลูป while first last และnot foundให้ทำดังนี้ 5.คำนาณค่าตัวแปร locมีค่ากับ(fist + last)/2 6.ถ้าค่า item ที่ต้องการหาน้อยกว่าX[loc] ทำดังนี้ 7.กำหนดตัวแปร last มีคากับ loc+1 8.ไม่เช่นนั้นถ้าค่า item ที่ต้องการหามากกว่า X[loc] ทำดังนี้ 9.กำหนดตัวแปร firstมีค่าเท่ากับ loc+1 10.ไม่เช่นนั้นกำหนดตัวแปร found มีค่ากับ true |
จากอัลกอริทึมนี้จะเห็นว่าประโยคบรรทัด 1 , 2 และ 3 มีการทำงานเพียงครั้งเดียว การทำงานถัดไปใช้กับกรณีแย่ที่สุดในการทำนวณเวลา Ta(n) โดย พิจารณาจากจำนวณครั้งการทำงานวนลูปตั้งแต่ประโยคบรรทัด4 จนถึง10 ซึ่งในการทำงานแต่ละราบของการวนลูป ขนาดของรายการจะลดลงเหลือครึ่งหนึ่งไปเรื่อย ๆ
จนกว่าจะพบค่าที่ต้อง การ นื่องจากใช้กรณีแย่ที่สุดจึงค้นหาถึงรอบท้ายสุดที่รายการเหลือเพียงค่าเดียว ดังนั้นจำนวนครั้งในการวนลูปกับบวกจำนวน k ราบของการนลูปจนกราการเหลือเพียง คาเดียว
เนื่องจากขนาดของรายการที่เหลืเพื่อใช้ค้นหาในเราบที่ได้ n/2k และต้องเป็น
<2
ซึ่งจะได้ว่า
n< 2k+1
หรือเท่ากับ
Log2n < k+1
สิ่งที่ต้องการคือ จำนวนราบที่ผ่านมาซึ่งเป็นตัวเลขน้อยที่สุด คือ ในส่วนของlog2 เมื่อให้การทำงานเป็นกรณีแย่ที่สุดและค่าที่ต้องการหาจะมากกว่าแต่ละค่าของ X[0],…,X[n-1] จะได้ประโยคบรรทัด 4ทำงานไม่มากกว่า 1+ log2n ประโยค่บรรทัด 5,6,8,9ทำงานมากกว่า 1+ log2 n และประโยคบรรทัดที่ 7,10ไม่มีการทำงานเทากับ 0 เวลาที่ใช้ทำงานทั้งหมดจึงไม่มากกว่า 9+5 log2 n และได้เป็น
Tb(n)= O(log2 n)
จาก กัลป์กอริทึมทั้งสองแบบเวลาในการทำงานการค้นหาแบบเชิงเส้นมีลักษณะฃองเชิง ซ้อนเป็นO(n)และการค้นหาแบบแบ่งครึ่งมีแนะสิทธิภาพมากกว่าการค้นหาแบบเชิง เส้นสำหรับข้อมูลในรายการมีจำนวนมาอย่างไรก็ตาม จากการศึกษาพบว่าการค้นหาแบบเชิงเส้นมีประสิทธิภาพมากกว่าการค้นหาแบบแบ่ง ครึ่งก็ต่อเมื่อจำนายข้อมูลในรายการไม่มากกว่า 20
ตัวอย่างการเปรียบเทียบประสิทธิภาพ
จาก ตัวอว่างการหาค่าหารร่วมมากโดยใช้อัลกอริทึมของยูคลิดที่ผ่านมาเวลาที่ใช้ทำ งานในบรรทัด 1จำนวน 3ครั้งสำหรับการวนลูปโดยแต่ละรอบมีการเปรียบเทียบค่าการส่งค่า และการหารเหลือเศษหากพิจารณาสำหรับทุกค่าของ n ที่เป็นไปได้และ 1 ≤ n ≤m ในกรณีที่ดีที่สุดการทำงานมีเพียงครั้งเดียวที่บรรทัด1ในกรณีแย่ ที่สุดซึ่งจะได้ค่าหารร่วมมากเท่ากับ 1 เสมอได้เป็นดังในรูปที่ 8.4 โดยแสดงเฉพาะจำนวนการทำงานมากที่สุดในแต่ละช่วงสำหรับค่าที่อยู่ระหว่างช่วง เหล่านี้จำนวรการทำงานจะไม่มากกว่าจำนวนของ m ในลำดับถัดไป เช่น ให้ m =6 หรือ 7จำนวนการทำงานนกรณีแย่ที่สุดจะไม่มากกว่า4 ที่เป็นของ m =8
| m | n | จำนวนการทำงานของบรรทัด |
| 235
8 13 21 34 55 89 144 |
123
5 8 13 21 34 55 89
|
123
4 5 6 7 8 9 10 |
รูปที่ 8.4 จำนวนการทำงานของอัลกอริทึมของยุคลิดในกรณีที่แย่ที่สุดในแต่ละช่วง
จากรูป 8.4 แสดงเฉพาะค่าของ m ที่เป็นค่าน้อย ๆ แต่สำหรับทุกๆค่าของ m ที่น้อยกว่า1,000,000
ในกรณีที่แย่ที่สุดจำนวนการทำงานของบรรทัด 1 จะไม่มากกว่า 28 ครั้ง
เพื่อ ให้มีการเปรียบเทียบอัลกอริทึม การหาค่าหารร่วมมากของยูคลิดจึงมีอัลกอริทึมอีกรูปแบบหนึ่งที่ใช้หาค่าหาร ร่วมมากเช่นกันดังในคารางมรา8.8 โดยจะชิจารณาถึงประสิทธิภาพว่าเป็นอย่างไร
ตารางที่ 8.8 อัลกอริทึมการหาค่าหารร่วมมาก
| 1. กำหนดตัวแปร g มีค่าเท่ากับค่าที่น้อยกว่าระหว่างตัวแปร mและ n2.ถ้าตัว แปร g หารด้วยตัวแป mและnให้จบการทำงานและได้ g เป็นค่าหารร่วมมาก3.กำหรดค่า g = g-1 และไม่ทำงานต่อในรอบถัดไปที่บรรทัด 1 |
อัล กอริทคมนี้นะลดค่าของ gตามลำดับต่อเนื่องจนกว่าจะพบคาที่สามารถหารค่า ของ mและnลงตัว หากไม่พบค่าที่ตอ้งการจะจบลงเมื่อค่าของ g เท่ากับ 1ซึ่งเป็นค่าหารร่วมมากของ ทึก ๆ ค่าและเป็นกรณีแย่ที่สุดพิจารณาเส้นทางการ ทำงานของอัลกอริทึมนี้เมื่อให้m = 144 และ n =60 เป็นไปตามลำดับดังนี้
บรรทัด 1:g = 60 เป็นค่าที่น้อยที่สุดระหว่าง 144และ60
บรรทัด 2:144/60 =2 เหลือเศษ 24และ60/60 = 1 เหลือเศษ 0
บรรทัด 3:g = 59
บรรทัด 2:144/59 =2 เหลือเศษ 26และ60/59 = 1 เหลือเศษ 1
บรรทัด 3:g = 58
…
…
…
บรรทัด 3:g = 48
บรรทัด 2:144/48 =3 เหลือเศษ 0และ60/48 = 1 เหลือเศษ 12
บรรทัด 3:g = 47
…
…
…
บรรทัด 3:g = 17
บรรทัด 2:144/12 =12 เหลือเศษ 0และ60/12 = 5เหลือเศษ 0
การหารทั้งสองมีเศษเหลือเท่ากับ 0 จบการทำงานและค่าหารร่วมมากกับ 12
อัล กอริทึมนี้ทำงานถูกตอ้งรับค่าที่รับเข้ามาเป็นแบบเดียวกับตัวอย่างอัลกอริ ทึมของยูคลิด ถึงแม้การทำงานจะถึงจุดสิ้นสุดแต่มีแระสิทธิภาพน้อยกว่าเนื่องจากการทำงานวน ซ้ำถึง49 ครั้ง แต่ละครั้งมีการหารเหลือเศษ 2ครั้งเดียวกับการเปรียบเทียบค่า3ครั้งในการวนลูปหากเป็นกรณีดีที่สุดจะทำ งานเพียงครั้งเดียวที่บรรทัด2 ส่วนใหญ่กรณีแย่ที่สุดเกิดขึ้นเมื่อn =m -1 และ mเป็นเลขขั้นข้อมูล (Prime Number)ซึ่งจำนวนการทำงานขอบรรทัด2เท่ากับ m-1 ครั้งอัลกอริทึมนี้เขียนเป็น ตัวอย่างโปรแกรมได้เป็นตารางที่ 8.9
ตารางที่ 8.9 โปรแกรมการหาค่าหารร่วมมาก
| #include <stdio.h>#include<stdlib.h>#include <conio.h>
intgcd (int m, int n) { int g; if(m < n) g=m; else g=n; while (g>1){ if((m%g==0)&&(n%g==0); return g; g–; } return 1; } main() { intm,n; printf(“Enter fist positive integer :”); scanf(“%d”,&m); printf(“Enter fist positive integer :”); scanf(“%d”,&n); printf(“\nGCDof %dand%dis %d\n”,m,n,gcd(m,n)); getch(); } |
ลักษณะเชิงซ้อนของอัลกอริทึม
การ วัดผลประสิทธิภาพของอัลกอริทึมโดยใช้เวลาในการทำงานเพื่อให้งานสำเร็จเผ็น การประมาณการของเวลาที่ต้องใช้ซึ่งมีอยู่ 2 วิธีคือ นับการดำเนินการ(Operation Count) จะแยกแยะการดำเนินการของคำสั่งและนับจะนวนเวลาที่ใช้ดำเนินการสั้น อีกวิธีคือนับขั้นตอ(Step Count) จะนับจำนวนเวลาของขั้นตอนการทำงานทั้งหมดในโปรแกรมดังในตัวอย่างที่ ผ่านมาใช้วิธีนี้ซึ่งเห็นผลสำคัญที่นำมาใช้เพื่อคาดการณ์ล่วงหน้าถึงการเติบ โตของเวลาที่ใช้ทำงานเมื่อของมูลมีจำนวนมากขึ้นและใช้เปรียบเทียบเวลาการทำ งานของสองโปรแกรมที่แก้ปัญหางานแบบเดียวกัน โดยมีเครื่องหมายที่นำมาใช้ 3ลักษณะคือ
1 เครื่องหมายบิ๊กโอ(Bigoh Notat6ion ,O) แสดงเป็น f(n)= O(g(n)) หมายความว่าเวลาการทำงานของ f(n) น้อยกว่าหรือเท่ากับ g(n)และได้ว่า g(n)เป็นขอบเขตด้านบนของ f(n)
2 เครื่องหมายโอเมก้า(Onega Notat6ion ,) แสดงเป็น f(n)= (g(n))หมายความว่าเวลาการทำงานของ f(n) มากกว่าหรือเท่ากับ g(n)และได้ว่า g(n)เป็นขอบเขตด้านบนของ f(n)
3 เครื่องหมายเตตตะ(Theta Notat6ion ,) แสดงเป็น f(n)= (g(n))หมายความว่าเวลาการทำงานของ f(n) เท่ากับ g(n)
ใน การเปรียบเทียบอัลกอริทึมโดยส่วนใหญ่ใช้เครื่องหมายบิ๊กโอซึ่งอธิบายของเขต ด้ายบน ในลักษณะเชิงซ้อนที่มีอัตราการเติบโคตรของฟังก์ชันfไม่สิ้นสุด (Asymptotic Complexity)และเวลาการทำงานไม่เกินของเขตลนี้ไปได้ให้ฟังก์ชันf และ g มี เลขบวกสองตัวและข้อกำหนดมีดังนี้
f(n) เป็น O(g(n))ถ้ามีค่าคงที่ c และ Nเป็นเลขบวกดังนั้น f(n) ≤ cg(n) สำหรับทุกๆ n โดย n ≥ N
หมายความว่า fหน้า 138
