Google         youtube            psv            สพม.11

ประสิทธิภาพการทำงานของอัลกอริทึม

ประสิธิภาของอัลกอริทึม โดยทั่วไปมีมตรฐานการวัดผลสองแบบโดยแบบแรกคือ การใช้พื้นที่ว่าง (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 ≤ 2n+ 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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s