อัลกอริทึม
การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบทที่ 1 มี 2 ส่วนที่สำคัญคือการเลือกใช้โครงสร้างข้อมูลและการออกแบบอัลกอริทึม (Algorithm) ซึ่งที่ผ่านมาได้กล่าวถึงโครงสร้างข้อมูลพื้นฐานแบบต่างๆ และในบทนี้จะกล่าวถึงรายละเอียดของอัลกอริทึมโดยพิจารณาวิธีการตรวจสอบการทำงานของอัลกอริทึมว่ามีความถูกต้องมากน้อยเพียงใดซึ่งใช้เทคนิคแบบการตรวจสอบความจริง (Verification) นอกจากมีการพิจารณาเปรียบเทียบหลายๆ อัลกอริทึมที่ใช้แก้ปัญหาเรื่องเดียวกันว่ามีประสิธิภาพต่างกันอย่างไรซึ่งมีเทคนิคที่นำมาใช้ตรวจวัดว่าอัลกอริทึมไหนดีกว่ากัน
การตรวจสอบความถูกต้องของอัลกอริทึม
การเรียกให้โปรแกรมหรือระบบทำงานแบบเบื้องต้นเพื่อทดสอบกับข้อมูลที่หลากหลาย ยังไม่มีประสิทิภาเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฎอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่รากฎจำม่สามารถทราบได้จึงนำการตรวจสอบแบบการอนุมาน (Deductive) มาใช้เพื่อรับประกันว่าผลลัพฑ์มีความถูกต้อง
การตรวจสอลอัลกอริทคึมเพื่อใช้แก้ไขปัญหาว่ามีความถูกต้องจึงใฃ้การอนุมานซึ่งแสดงขั้นตอนการประมวลผลของอัลกอริทึมถูกต้องหรือไม่ตั้งแต่มีการรับข้อมูลเข้ามาและแก้ปัญหาจนถุงผลลัพธ์ที่ได้ออกมา ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึม A เรื่มต้นด้วยการวินิจฉัย I เป็นการสมมุติข้อมูลี่จะรับเข้ามาใช้งาน (Input Assertion) เรยกว่าเงื่อนไขตอนต้น(Precondition) และการวินจฉัย O เป็นการสรุปผลลัพธ์ที่ได้ออกมา (Output Assertion)เรียกว่าเงื่อนไขตอนท้าย ( postcondition)ได้เป็นขอ้พิสูจน์ทางตรรกะแสดงให้ทราบว่า Oจะเกิดขึ้นตาม I และได้เป็น
I => O (“I Implies O”)
ได้หลัเกณฑ์ คือ เมือกำหนดเงื่อนไขต้น I หลังจากอัลกอริทึม A ทำงานจนถึงงจุดสิ้นสุด (Terminate)จะต้องได้เงื่อนไขตอนท้าย O โดยพิจารณาจากตัวอย่างอีลกอริทึมหม่าฉลี่ยของค่าทั้งหมดที่เก็บไว้อาร์เรย์ดังในตารางที่ 8.1
ตารางที่ 8.1อัลกอริทึมการทึมการำนวณหาค่าฉลีย
1. กำหนดค่าเรื่มต้นให้ตัวแปร sum =0
2. กำหนดค่าเรื่มต้นให้ตัวแปรดัชนั i=0
3. วนลูป while i<n ให้ทพดังนี้
a. นำค่าของอาร์เรย์ X[i] บวกกับตัวแปร sum
b. เพิ่มค่าให้กับตัวแปร I หนึ่งค่า
4. คำนวณหาค่าเฉลี่ย sum/n และส่งคืนกลับ
เมื่อวินิจฮัยการรับค่า I จะได้คำอธิบายดังนี้
I :ค่าที่รับเข้ามาประกอบด้วยตัยเลข n ≤ 1 และอาร์เรย์ Xที่เก็บค่าเลขทศนิยมเมื่อวินิจฉียผลลัพท์ oออกมาจะได้คำอธิาย
O: อัลกอริทึคมทำงานเสร็จ ค่าที่ส่งคอนกลับมาให้เป็นค่าเฉสี่ยของX[0],…,X[n-11]
การแสดงผลการทำงานจะได้ว่าเงื่อนไขตอนท้าย O จะเกิดขึ้นได้ตามเงื่อนไขตอนต้น I และมีหลายช่วงของอัลกอริทึมซึ่งเป็การวินิจฉัยซึ่งเป็นการวินิจฉัยตอนกลาง (Intermediate Assertion) โดยเกี่วกับสถานะของการประมวลผลเมื่อทำงานถึงในช่วงนั้น ๆ จากตัวอย่างอัลกอริทึมที่ผ่านมามีการวินิจฉัยตอกลาง L ในส่วนท้ายของการวนลูป while ซึ่งจะเป็นจริงทุกครั้งเมื่อการทำงานมาถึงช่วงนี้และการวินิจฉัยตอกลางี้เรียกว่าการวนลูปสม่ำเสมอ (Loop Invariant) จะได้ว่า
I: ค่าที่รับเข้ามาประกอบด้วยตัเลข n ≥ 1 และอาร์เราย์ X ที่เก็บค่าเลขทศนิยม
1 . กำหนดค่าเริ่มต้นให้ตัวแปร sum =0
2. กำหนดค่าเริ่มต้นให้วแปรดัชนี i=0
3. while i<n ให้ทำดังนี้
a. นำค่าของอาร์เรย์ X [i] บวกให้กับตวแปร Sum
b. เพิ่มค่าให้กับตัวแปร I หนึ่งค่า
L : ค่าของตัวแปร I เป็นจำนวนครังในการทำงานที่ถึงในแต่ละช่วง และตัวแปร sum เป็นผลลรวม่าของแตลสมาชิก I ในอร์เรย์ X
4. คำนวณหาค่าเฉสี่ย Sum /n และส่งค่ากลับ
O :อัลกอริทึมทำงานเสร็จ ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉสี่ยของ X[0],…,X[n-1]
การตรวจสอบจึงประกอบด้วยการแสดงคำอธิบายใหทราบว่าการวินิจฉัย Lได้โดยสมติให้ k เป็นจำนวนครั้งในการทำงานที่ถึงส่วนล่งของการวนลูปให้ ik และ sumk เป็นค่าของตัวแปร i และ sum ตาม่ลำดับของแตละครั้งทีทำงานมาถึง เมี่อ k=1 เป็นการผ่นรอบแรกในลูปค่าของ iมีค่าเป็น 0 จากค่าเริ่มต้นกับ 0(บรรทัด 1) ตัวแปร sum มีค่าเทากับ X[0] (บรรทัด 3a)ซึ่งค่าเริ่มต้นเท่ากับ 0(บรรทัด 1) จากนั้นเพิ่ค่าให้กับตัวแปร I หนึ่งค่าจได้ i=1 (บรรทัด 3b)ดังนั้นจะได้ว่าตัวแปร I และ sum มีค่าที่ถูกวินิจฉัยของ L เมื่อ k=1หากสมมุติให้การทำงานเมื่อไปถึงส่วนล่างของการวนลูปสำหรับครั้งที่ k การวนลูปสม่ำเสมอของ L ได้เป็น ดังนี้
Ik =kและ sumk =X[0] +….+X[k-1]
ซึ่งสามารถตรวจสอบได้ว่า l เป็นรจริงเช่นกันเมื่อการทำงานต่อไปผ่านไปถึงการวนลูปในครั้งที่ k+1 ซึ่งได้เป็น
Ik+1 =k+1และ sumk+1 = X[0] +….+X[k-1]
ในรอบที่k +1 เมื่อผ่นการวนลูปค่าของ I มีความถูกต้งเพื่อใช้งานดงนี้
Sumk+1 =sumk +X[k] (บรรทัดที่ 3a )
=X[0]+…+X[k] (การอนุมานสมมุติ)
และค่าของ I จะเพิ่มขึ้นหึ่งค่าดังนี้
Ik+1=ik+1 (บรรทัดที่ 3b)
= k+1 (การอนุมานสมมุติ)
จากนี้เมื่อทำค่อเนื่องโดยการอนุมานไปแต่ละครั้งการทำงานไปถึงส่วนล่างของการวนลูปค่าของตัวแปร I และ sum จะถูกวินิจฉัยในการวนลูปสม่ำเสมอ หลังจากการวนลูปทำงานผ่านนิพจน์ i<nซึ่งคบคุการทำงานซ้ำในลูปเป็นเท็จ ลูป while จึงหยุดการทำงานและทำต่อที่ บรรทัด 4 เป็นการคานวณหาค่าฉลี่ยของสมาชิกในอาร์เรย์ จากนั้นการทำงานถึงจุดสิ้นสุดของอัลกอริทึมและนำการวินิจฉัยผลลัพธ์มาใช้ ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึมจึงเสร็จสิ้นสมบูรณ์
การตรวจสอบดังกล่าวมีสักษระเรยบง่ายซึ่งมีการวินิจฉับตอนกลาง L เพียงตอนเดียว และอยู่ในรูปแบบต่อไปนี้
I=>L=> O
แต่สักหรับอัลกอริทึมที่ซับซอ้นมากขึ้นจำเป็นต้องมีการวินิจฉัยตอนกลางหลาย ๆ ตอน คือ L1, L2, …, Ln ดังนั้น อัลกอริทึมหรือโปรแกรมจึงถ฿กแตกออกมาเป็นส่วน ๆ เรียกว่าเซ็กต์เม้นท์ (Segment)ซึ่งอาจเป็นประโยคคำสั่งเดีวบล็อกการวนลูป หรือทั้งโปรแกรม โด่ยแต่ละเซ็กต์เม้นท์จะมี Li หรือ I เป็นเงื่อนไขตอนต้นและมี Li+1 หรือ O เป็นเงื่อนไขตอนท้ายดังในรูปที่ 8.1
Li
Li+1
รูปที่ 8.1 เซ็กต์เม้นนท์กับเงงื่อนไขตอนต้น และเงื่อนไขตอนท้าย
ถ้าให้ Li+1 เกิดขึ้นมาตาม Li สำหรับแต่ละ i=1,…,n-1 ใจได้โครงสร้างของการตรวจ สอยความถูกตอ้งเป็น ดังนี้
I=> L1 => L2=>…=>Ln=> O
หากเซ็กต์เม้นท์ของโปรแกรมมีโครงสร้างการทำงานแบบเรียงลำดับ (Sequential)การตรวจสอบความถูกตอ้งจะทำทีละประโยคคำสั่งตามลำดับ ถ้ามีโครงสร้างการทำงานเป็ทางเลือกหรือเงื่อนไข (if)ก็จะมีหลายเส้นทางการทำงานเป็นไปได้เดระหว่างจาก Li ไปยังLi+1
และมีความจะเป็นจะต้องตรวจสอบเส้นทางการทำงานทั้งหมด ทำให้การตรวจสอบความถูกต้องมีความซับซ้อนมากขึ้น ซึ่งต้งใช้เวลาและความพยายามเพื่อตรวจสอบอย่างอลเอียดเพื่อให้เกดตวามถูกต้อง หากโครงสร้างการทำงานเป็นการวลูป การตรวจสอบจะทำในแต่ละรอบโดยมีตัวควบคุมการวนลูป (Sentinel-contolled Loop)ตัวควบคุมนับจำนวนการวนลูป (Count-controlled Loop)เละเงื่อนไขการวนลูปทั่วไป(General Condition Loop)ซึ่งเป็นการทำงานอื่นๆ ในลูปและช่วยการตรวจสอบ โครงสร้างการทำงานสุดท้ายของเซ็กต์เม้นท์ คือ การเรียกฟังก์ชันมาทำงาน (Function Call) ในการตรวจสอบความถูกต้องจะใช้ค่าพารามิเตอร์ต่าง ๆ เป็นเงื่อนไขตอนต้น ค่าต่าง ๆ ที่ต้องส่งกลับคืนมาเป็นเงื่อไขตอนท้าย และตัวฟังก์ชันเป็นการวินิจฉัยตอนกลาง
ดังนั้น ทางเลือกการเขียนแรแกรมที่ดีจึงต้องมีการวางกฎเกณฑ์ในการวินิจฉัยลัคเนินการตรวจสอบตามแนวทางที่วางไว้ และถึงแม้ว่าไม่สามารถรับประกันว่าอัลกอริทึมจะทำงานถูกต้องอย่างสมบูรณ์ แก็ทำให้ผู้เขียนโปรแกรมมีความเข้าใจอัลกอริทึมมากขึ้นและเกิดความมั่นใจในการทำงานที่ถูกต้องหลังจากได้มีการตรวจสอบ
ตัวอย่างการตรวจสอบอัลกอริทึม
ในปี ค.ศ. 1950 คำว่าอ้ลกอริทึมได้ถูกนำมาใช้กับอัลกอริทึมขิงยูคลิด (Euclid’s Algorithm) เป็ฯการหาค่าหารร่วมมาก (ห.ร.ม.)ซ฿งเป็ฯค่าสูงสุดที่สามารดนำไปหารค่าสองค่าได้ลงตัว (Greatest Common Divisor : GCD)ได้เป็นอัลกอริทึมดังในตารางที่9.2 โดยมีการรับค่าตัวเลขบวก mและnเพื่อหาค่าหารร่วมมาก ตัวเลขที่รับเข้ามานี้ค่าที่มากกว่าจะว่าจะถูกหารด้วยค่าทีนอยกว่า
ตารางที่ 8.2 อเลกอริทึมของยูคลิด
1 . หารตัวแปร m ด้วยตัวแปร n และเก็บค่าเศษที่เหลือให้กับตัวแปร r
2. ถ้าตัวแปร r = 0ให้จบการทำงานและได้ n เป็นค่าหารรวมมาก
3. กำหนด ค่า m = n ,n = r และไปทงานต่อในรอบถัดไปที่บรรทัด 1
อัลกอริทึมอื่น ๆ และของยูคลิดเป็นชุดการทำงานเพื่อใช้งานหรือแก้ไขปัญหาบางอย่างโดยการทำงานต้องมีขอบเขตที่สามารถไปถึงจุดสิ้นสุด (Terminate) ได้โดยเฉพาะต้องระมัดระวังการวนลูปที่ไม่สิ้นสุด ( Endless Loop) หากพิจารณาจากอัลกอริทึมของยูคลุดซึ่งกำหรดให้ m= 144 และ n=60 จะได้ว่าค่าทั้งสองถูกตอ้งเพราะเป็นค่าบวกตามเงื่อนไขตอนต้นและการทำงานของัลกอริทมเป็นารวนลูปสม่ำเสร โดยแต่ละบรรทัดถูเรียกให้ทำงานเป็นไปตามลำดับ ดังนี้
บรรทัดที่ 1: r=240 จากการหาร 146/60=2 เหลือเศษ24
บรรทัดที่ 2: r ไม่เท่ากับศุนย์
บรรทัดที่ 3: m =60 ,n=24
บรรทัดที่ 1: r =12 จากการหาร 60/24=2 เหลือเศษ12
บรรทัดที่ 2: rไม่เท่ากับศุนย์
บรรทัดที่ 3: m =24 ,n=12
บรรทัดที่ 1: r=0 จากการหาร 24/12=2 เหลือเศษ0
บรรทัดที่ 2: r เท่ากับศุนย์นการทำงานและค่าหารร่วมมากเท่ากับ 12
จากการตรวจสอบลำดับการทำงาตั้แต่เงื่อนไขตอนต้นที่ถูกต้อง และการทำงานของวนลูปสม่ำเสมอในตอนกลางจนถึงเงื่อนไขตอนท้ายจะได้ค่า 12 เป็นค่าหารร่วมมากของค่า 144และ 60 ดังนั้นอัลกอริทึมนี้ที่งานได้ผลตามที่ตัองการทำงานของอัลกอริทึมที่ถูกต้องและได้ผลตามที่ต้องการในทุกกรณี การเขียนโปรแกรมจึงต้องมีการตรวจสอบความถูกต้องของการทำงานโดยทดสอบช่วงของค่าที่รับเข้ามากับค่าที่เป็นผลลัพธ์ออกมา ถ้าโปรแกรมผ่านการทดสอบทุกรูปแบบที่เป็นไปได้ ก็จะทำให้ผู้เขียนโปรแกราเกิดความมั่ใจ
อัลกอริทึมของยูคลิดมีการทำงานที่ถึงจุดสิ้นสุด คือ ค่าที่เหลือเก็บไว้ที่ r น้อยกว่าค่าของ n และถ้าเริ่มต้นให้ n < m ในแต่ละรอบการวนลูปทั้งค่าของ m และ n จะถูกแทนด้วยค่าที่น้อยกว่าซึ่งค่าใหม่ของ m ยังคงมากกว่าค่าของ n จะน้อยลงเรื่อย ๆ จนเงื่อนไขที่ค่าของ r = 0 เป็นจริง ในกรณีโชคร้ายหรือแย่ที่สุดคือ ค่าของ n ลดลงเป็น 1 หากพบว่าเริ่มต้นค่าของ n > m จะมีการสลับค่ากันละหว่าง m กับ n โดยอัลกอริทึมของยูคลิดเขียนเป็นตัวอย่างโปรแกรมได้เป็นตารางที่ 8.3
ตารางที่ 8. 3 การหาค่าหารร่วมมาก
#include <stdio.h>
#include <stelib.h>
#include <conio.h>
int euclid <int m, int n) {
int em;
rem =m%n;
while(rem !=0 ){
m = n ;
m =rem;
rem = m%n;
}
retutn n;
}
main(){
int m,n ;
printf(“Enter first positive integer : “);
scanf(“%d”,&m);
printf(“Enter first positive integer : “);
scanf(“%d”,&n);
printf(“\nGCD of %d and %d is %d \n “,m,n,euclid(m,n));
getch ();
}
ประสิทธิภาพการทำงานของอัลกอริทึม
ประสิธิภาของอัลกอริทึมโดยทั่วไปมีมตรฐานการวัดผลสองแบบโดยแบบแรก คือ การใช้พื้นที่ว่าง (Space Utilization)เป็นจำนวนของหส่วยความจำที่ต้องการใช้เพื่อให้งานสำเร็จประกอบด้วยพื้นที่เก็บคำสั่งทา นที่เก็บข้อมูล และพื้นที่สภาวะแวดลอ้มสแตกแบบที่ 2 คือประสิทธิภวะเวลา (Time Efficiency) เป็นจำนนของเวลาที่ต้องกรใช้การประมวลผลข้อมูลเพื่อให้งานสำเร็จ การสำทั้งสองแบบมาวัดปลด้วยันไม่สามารถเป็นไปได้ เนื่องจากอัลกอริทึมที่ขอใหชื้นที่หน่วยความจำได้ต้อ่ยกว่ามักจะทำงานช้ากว่าอัลกอริทึมที่ขอได้มากกว่า ดังนั้น ผู้เขียนแรแกรมจึงต้งเลือกว่าจะใช้การขอในที่ว่างหรือประสิทธิภาพเวลา แต่แระสิธิภาพเวลาของอัลกอริทึมจะมีความสำคัญกว่าจึงนำมาใช้พิจารณา ซึ่งเวลาที่ใช้ในการทำงานของอัลกอริทึมชขึ้นกับปัจจัยหลายๆอย่าง ดังนี้
1.ขนาดข้อมูลที่รับเข้ามา จำวนของข้อมูลที่รับเข้ามาทำงานจะมีผลกระทบต่อเวลาที่ใช้ทานใจนการปรมวลลข้อมูลที่รับเข้ามา เช่น เวลาที่ใช้จัดเรียงลำดับข้อมูลของรายการขึ้นกับจำนวนของข้อมูลที่มีอยู่ในรายการ ( รายละเอียดการจัดเรียงงลำดับอยู่ในบทที่ 11) ดังนั้น เวลาในทำงาน T ของอัลกอริทึมจะแสดงในรูปแบบฟังก์ชัน T(n)ของข้อมูลที่รับเข้ามามีขนาด n ค่า
2. ขนิดของเครื่องคอมพิวเตอร์ คำสั่ง (Instruction)และความเร็วของคอมพิวเตอร์มีผลต่อเวลาในการทำงาน ปัจจัยนี้ขึ้นกับเครื่องคอมิวเตอร์ที่นำมาใช้ ซึ่งไม่สามารถคาดคะเนให้ความหมายเวลา T(n)อยู่ในลักษณะของเวลาที่เป็นจริง(วินาที)แต่จะนับจำนวนของคำสั่งที่ใช้ในการทำงานโดยประมาณเป็นเวลาT(n )แทน
3. คุณภาะซอรสโค้ดและคอมไพเลอร์ เป็นอีกปัจจัยหนค่งที่มีผลต่อเวลาทีใช้ทำงานซึ่งขึ้นกับคุณภาพของซอร์สโคด้ (Source Code) ที่เขียนการทำงานเป็นอัลกอริทึมและคุณภาพของคอมไพเลอร์(Compiler)ในการแปลงซอร์สโค้ดไปเป็นโค้ดถกษาเครื่อง(Machine Code ) ในบางภาษาเขียนโปแกรมมีความเหมาะสมกว่าในการเขียนอัลกอริทึมในขณะที่บางภาษามีคอมไพเลอร์ที่แปลงงโค้ดได้ดีกว่า ซึ่งหมายความว่าค่า T(n)ไม่สามารถจะทราบได้เมื่อไช้กับการนับจำนวนของคำสั่งในการทำงาน(ข้อ 2)
ประสิทธิภาพกับขนาดข้อมูลที่รับเข้ามา
ตัวอย่างต่อไปนี้เป็นอัลกอริทคมที่ได้กล่าวมาแลวนารางที่ 8/.1 เป็นการคำนวนหาค่าเฉลี่ยจากการรับค่าเข้ามา n ค่าท่เก็บไว้ในอาร์เรย์ และมีการกำหนดหมายเลขบรรทัดให้กับและประโยคเพื่อความสะดวกในการอ้างถึงได้เป็นดังในตารางที่ 8.4
ตารางที่ 8.4 อัลกอริทึมการคำนวนหาคาเฉลี่ย
1.กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2.กำหนดค่าเริ่มต้นให้ตัวแปรดับนี i =0
3. วนลูป 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
ประโยค #
จำนวนการทำงาน
1
2
3
4
5
6
1
1
n+1
n
n
1
ยอดรวม
3n+4
รูปที่ 8.2จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่ 8.2
จะเห็นว่าเวลาที่ใช้ในการทำงานของอัลกอริทึมนี้ได้เป็น
T(n) =3n+4
เมื่อจำนานข้อมูลที่รับเข้ามาเพิ่มขึ้น ค่าเวลาในการทำงานของ T(n) ก็จะเพิ่มมากขึ้นตามอัตราส่วนของ nและได้ว่า T(n) มีลำดับขาดตามค่าของ nซึ่งกำหนดเป็นสัญลักษณ์เครื่องหมายบิ๊โอ (Big Oh 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ในช่วงใดช่วงหนึ่ง และการคำนวนเชิงซ้อน (Computational Complexity)ของอัลกอริทึมเรียกเป็น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 มีค่าเท่ากับ i
3. 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 อับกอริทึมการค้นหาแบบเชิงเส้น
การหนดตัวแปร found มีค่าเท่ากับ false
กำหนดตัวแปร Ioc มีค่าเท่ากับ 0
วนลูปwhile Ioc ≤ n -1 และ not found ให้ทำดังนี้
ถ้า X[Ioc] มีค่าเท่ากับ item ที่ต้องการหาคำดังนี้
กำหนดตัวแปร found มีค่าเท่ากับTrue
ไม่เช่นนั้น เพิ่มหนึ่งค่าให้กับตัวแปร Ioc เท่ากับ Ioc+1
ในกรณีแย่ที่สุดของการค้นหาคือ ไม่พบค่าที่ต้องการมีอยู่ในรายการ ซึ่งใช้เวลาการทำงาน TL(n)สำหรับอัลกอริทึมการค้นหาแบบเชิงเส้นในรูที่ 8.3
ประโยค #
จำนวนการทำงาน
1
2
3
4
5
6
1
1
n+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 มีค่าเท่ากับfalse
2.กำหดตัวแปร first มีค่าเท่ากับ 0
3.กำหดตัวแปร 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
หรือเท่ากับ
Log2 n < k+1
สิ่งที่ต้องการคือ จำนวนราบที่ผ่านมาซึ่งเป็นตัวเลขน้อยที่สุด คือ ในส่วนของ log2 เมื่อให้การทำงานเป็นกรณีแย่ที่สุดและค่าที่ต้องการหาจะมากกว่าแต่ละค่าของ X[0],…,X[n-1] จะได้ประโยคบรรทัด 4ทำงานไม่มากกว่า 1+ log2 n ประโยค่บรรทัด 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
จำนวนการทำงานของบรรทัด
2
3
5
8
13
21
34
55
89
144
1
2
3
5
8
13
21
34
55
89
1
2
3
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และ n
2.ถ้าตัวแปร 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>
int gcd (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() {
int m,n;
printf(“Enter fist positive integer :”);
scanf(“%d”,&m);
printf(“Enter fist positive integer :”);
scanf(“%d”,&n);
printf(“\nGCD of %d and %d is %d \n”,m,n, gcd(m,n));
getch();
}
ลักษณะเชิงซ้อนของอัลกอริทึม
การวัดผลประสิทธิภาพของอัลกอริทึมโดยใช้เวลาในการทำงานเพื่อให้งานสำเร็จเผ็นการประมาณการของเวลาที่ต้องใช้ซึ่งมีอยู่ 2 วิธีคือ นับการดำเนินการ(Operation Count) จะแยกแยะการดำเนินการของคำสั่งและนับจะนวนเวลาที่ใช้ดำเนินการสั้นอีกวิธีคือนับขั้นตอ(Step Count) จะนับจำนวนเวลาของขั้นตอนการทำงานทั้งหมดในโปรแกรมดังในตัวอย่างที่ผ่านมาใช้วิธีนี้ ซึ่งเห็นผลสำคัญที่นำมาใช้เพื่อคาดการณ์ล่วงหน้าถึงการเติบโตของเวลาที่ใช้ทำงานเมื่อของมูลมีจำนวนมากขึ้น และใช้เปรียบเทียบเวลาการทำงานของสองโปรแกรมที่แก้ปัญหางานแบบเดียวกัน โดยมีเครื่องหมายที่นำมาใช้ 3ลักษณะ คือ
1 เครื่องหมายบิ๊กโอ (Big oh 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
การแก้ปัญหาโจทย์ทางคอมพิวเตอร์
ขั้นตอนการแก้ไขปัญหาทางคอมพิวเตอร์ 1. การนิยามปัญหา (Problem Definition) ในขั้นแรกของการแก้ปัญหา สิ่งสำคัญที่สุด คือเราต้องทำความเข้าใจให้ได้ว่าปัญหาคืออะไร ประเด็นหลักอยู่ที่ใด และต้องการให้ได้ผลลัพธ์อะไร 2. การวิเคราะห์ปัญหา (Problem analysis) หลังจากที่เข้าใจปัญหาได้ดีแล้ว ขั้นต่อไป คือ การวิเคราะห์ปัญหา และพัฒนาสูตรเชิงคณิตศาสตร์ที่แทนวิธีการแก้ปัญหา วิเคราะห์ปัญหา ให้พิจารณาที่ผลลัพธ์ของปัญหาก่อน (output) ว่าคืออะไร และมีข้อมูลนำเข้า (input) อะไรบ้างที่จะทำให้ได้ผลลัพธ์เช่นนั้น จากนั้นจึงคิดสูตรเป็นสมการ หรือวิธีการที่จะแก้ปัญหานั้น เราต้องวิเคราะห์ให้ได้ว่า ข้อมูลอะไรที่นำเข้าจากผู้ใช้ ข้อมูลอะไรเกิดขึ้นจากการคำนวณ หรือข้อมูลใดเป็นค่าคงที่ ตัวอย่างเช่น โจทย์ต้องการให้เขียนโปรแกรมคำนวณหาจำนวนเงินที่ต้องการจ่ายให้พนักงานรายวัน แต่ละคน โดยมีค่าแรงเป็น 40 บาทต่อชั่วโมง ถ้าทำงานเกินจะมีค่าล่วงเวลาคิดเป็นอัตรา 7 บาทต่อชั่วโมง จากโจทย์ ผลลัพธ์ที่ต้องการ คือ จำนวนที่ต้องจ่ายให้แก่พนักงาน ข้อมูลนำเข้า คือ จำนวนชั่วโมงที่ทำงาน จากนั้นนำมาเขียนเป็นสูตร เชิงคณิตศาสตร์ดังนี้ ค่าแรงของพนักงาน = จำนวนชั่วโมงที่ทำงาน *40 "ถ้าจำนวนชั่วโมงน้อยกว่าหรือเท่ากับ 8" ค่าล่วงเวลา = (จำนวนชั่วโมงที่ทำงาน -8)*7 "ถ้าจำนวนชั่วโมงมากกว่า 8 ชั่วโมง" รวมจำนวนเงินค่าแรงของพนักงานแต่ละคน = ค่าแรงของพนักงาน + ค่าล่วงเวลา 3. การออกแบบอัลกอริธึม (Algorithm design) หรือการออกแบบขั้นตอนวิธีการแก้ปัญหา ในขั้นนี้เป็นการคิดหาขั้นตอนการแก้ปัญหาทีละขั้น เราต้องคิดว่าจะทำอย่างไรจึงจะแก้ปัญหาได้ และสามารถนำมาแปลงเป็นคำสั่งของภาษาโปรแกรมได้โดยง่าย ซึ่งเรียกขั้นตอนการแก้ปัญหาทีละขั้นนี้ว่าอัลกอริธึม (algorithm) ตัวอย่างจากโจทย์การคำนวณหาจำนวนเงินที่ต้องการจ่ายให้แก่พนักงาน เขียนอธิบายแต่ละขั้นไดดังนี้ ขั้นที่ 1 รับข้อมูลชั่วโมงทำงานของพนักงานจากแป้นพิมพ์ ขั้นที่ 2 เปรียบเทียบจำนวนชั่วโมงทำงานกับ 8 ถ้าจำนวนชั่วโมงทำงาน มากกว่า 8 แล้ว ให้คำนวณตามสูตรต่อไปนี้ ค่าแรงของพนักงาน = 8*40 ค่าล่วงเวลา = (จำนวนชั่วโมงที่ทำงาน – 8 ) *7 ถ้าจำนวนชั่วโมงทำงาน น้อยกว่าหรือเท่ากับ 8 แล้วให้คำนวณ ค่าแรงของพนักงาน = จำนวนชั่วโมงที่ทำงาน * 40 ค่าล่วงเวลา = 0 ขั้นที่ 3 คำนวณจำนวนเงินที่ต้องจ่ายให้แก่พนักงาน รวมจำนวนเงินค่าแรงของพนักงานแต่ละคน = ค่าแรงของพนักงาน + ค่าล่วงเวลา ขั้นที่ 4 แสดงผลลัพธ์ให้ผู้ใช้ทราบ ขั้นที่ 5 จบการทำงาน แต่ละขั้นตอนต้องมีความชัดเจนว่าจะทำอะไร แล้วได้ผลลัพธ์อะไรในแต่ละขั้น 4. การพัฒนาโปรแกรม (Program development) ในขั้นตอนนี้นักเขียนโปรแกรมต้องนำเอาคำอธิบายของขั้นตอนการแก้ปัญหาแต่ละขั้นจากอัลกอริธึมมาแปลงเป็นคำสั่งของภาษาโปรแกรมคอมพิวเตอร์ภาษาใดภาษาหนึ่ง เช่น เขียนด้วยภาษา c++ เป็นต้น การพัฒนาโปรแกรมจะทำได้ง่าย ถ้าอัลกอริธึมถูกต้อง และมีความชัดเจน 5. การทดสอบความถูกต้อง (Program Testing) หลังจากที่เราเขียนคำสั่งของภาษาโปแกรมคอมพิวเตอร์แล้ว ขั้นต่อไป คือ การทดสอบ (Testing) เพื่อหาข้อผิดพลาดจากการเขียนคำสั่งผิดไวยกรณ์ของภาษา หรือข้อผิดพลาดจากการคำนวณการทดสอบควรทดสอบทุกกรณีที่คาดว่าจะเกิดขึ้น ตัวอย่างเช่น การคิดจำนวนเงินที่ต้องจ่ายให้แก่พนักงานเราต้องทดสอบด้วยการป้อนจำนวนชั่วโมงทำงานประมาร 3 ค่า คือ ค่าที่มากกว่า 8 หรือค่าที่น้อยกว่า 8 หรือค่าที่เท่ากับ 8 เพื่อทดสอบว่าถูกต้องทุกกรณีตามสูตรที่ออกแบบไว้หรือไม่ 6. การจัดทำเอกสาร (Documentation) การจัดทำเอกสารถือว่าเป็นงานที่สำคัญที่นักเขียนโปรแกรมส่วนใหญ่ละเลย การจัดทำเอกสารมีได้สองแบบ คือจัดทำเอกสารคู่มือผู้ใช้ และเอกสารคู่มือพัฒนา ซึ่งเอกสารแบบหลังนี้มีความสำคัญต่อองค์กร เพราะช่วยให้การบำรุงรักษาโปรแกรมทำได้ง่ายขึ้น และใช้อ้างอิงในกรณีที่มีการเปลี่ยนแปลงใด ๆ ในระบบ การเขียนหมายเหตุในโปรแกรมถือว่าเป็นสิ่งจำเป็นที่ควรจะทำ เพื่ออธิบายความคิดว่าขณะนั้นได้คิดอะไร การเขียนหมายเหตุเป็นสิ่งที่ช่วยเตือนความทรงจำของตัวผู้เขียนเอง และคนอื่น 7. การบำรุงรักษา และการแก้ไข (Maintenance and modification) การพัฒนาโปรแกรมขึ้นมาใหม่ถือว่าเป็นเรื่องที่ง่ายการการบำรุงรักษา และการแก้ไข ต้นทุนการบำรุงรักษาโปรแกรมจะเพิ่มมากขึ้นหากการออกแบบโปรแกรมทำได้ไม่ดี ตัวอย่างอัลกอริธึมคำนวณค่าแรง การระบุจำนวนชั่วโมง อัตราค่าแรง อัตราค่าแรงล่วงเวลาเป็น 8 และ 40 และ 7 ถ้าเราระบุแบบตายตัวเข้าไปในสูตร ในกรณีที่มีการเปลี่ยนนโยบาย เช่นอัตราค่าแรงเป็น 50บาท/ชั่วโมง อัตราค่าล่วงเวลา เป็น 10 บาท/ชั่วโมง ถ้าจำนวนบรรทัดคำสั่งไม่มากคงแก้ไขได้ไม่ยาก แต่ถ้าอัตราเหล่านี้ถูกนำไปใช้ในหลาย ๆ แห่ง ในแฟ้มคำสั่งคงจะยุ่งยากที่จะตามแก้ไขให้ครบสมบูรณ์ทุกแห่ง ดังนั้นการออแบบโปรแกรมใด ๆ ต้องให้มีลักษณะความยืดหยุ่น ปรับเปลี่ยนได้ง่ายเมื่อความต้องการเปลี่ยนเปลี่ยน ในอัลกอริธึม อาจเพิ่มตัวแปรเก็บค่าอัตราทั้งสองก็ได้ แล้วนำตัวแปรนั้นไปใช้ในทุกแห่งที่อ้างถึง เวลามีการเปลี่ยนค่าจะเปลี่ยนที่เดียวก็จะมีผลทุกแห่งที่อ้างถึงตัวแปรอัตราเหล่านั้น แก้ไขอัลกอริธึมใหม่ในขั้น 1, และ 2 ได้ดังนี้ ในขั้นที่ 1 เพิ่มบรรทัดคำสั่งต่อไปนี้ Rate
ไม่มีความคิดเห็น:
แสดงความคิดเห็น