สื่อการเรียนรู้ อัลกอริทึม
การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบทที่ 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 โดยพิจารณาจากตัวอย่างอีลกอริทึมหาค่าเฉลี่ยของค่าทั้งหมดที่เก็บไว้อาร์เรย์ดังในตารางที่ 1
ตารางที่ 1 อัลกอริทึมการทึมการำนวณหาค่าเฉลี่ย
เมื่อวินิจฮัยการรับค่า 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 จะเกิดขึ้นตามการรับค่าเข้ามาของการวินิจฉัย I และแสดงให้ทราบว่าการวินิจฉัย O จะเกิดขึ้นตามการวินิิจฉัย L
การอนุมานทางคณิตศาสตร์สามารถนำมาใช้กับการวนลูปสม่ำเสมอ 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 ได้เป็น ดังนี้
ซึ่งสามารถตรวจสอบได้ว่า l เป็นรจริงเช่นกันเมื่อการทำงานต่อไปผ่านไปถึงการวนลูปในครั้งที่ k+1 ซึ่งได้เป็น
ในรอบที่ k +1 เมื่อผ่นการวนลูปค่าของ I มีความถูกต้งเพื่อใช้งานดั้งนี้
และค่าของ I จะเพิ่มขึ้นหนึ่งค่าดังนี้
จากนี้เมื่อทำต่อเนื่องโดยการอนุมานไปแต่ละครั้งการทำงานไปถึงส่วนล่างของการวนลูปค่าของตัวแปร I และ sum จะถูกวินิจฉัยในการวนลูปสม่ำเสมอ หลังจากการวนลูปทำงานผ่านนิพจน์ i<n ซึ่งคบคุการทำงานซ้ำในลูปเป็นเท็จ ลูป while จึงหยุดการทำงานและทำต่อที่ บรรทัด 4 เป็นการคานวณหาค่าฉลี่ยของสมาชิกในอาร์เรย์ จากนั้นการทำงานถึงจุดสิ้นสุดของอัลกอริทึมและนำการวินิจฉัยผลลัพธ์มาใช้ ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึมจึงเสร็จสิ้นสมบูรณ์ การตรวจสอบดังกล่าวมีสักษระเรยบง่ายซึ่งมีการวินิจฉับตอนกลาง L เพียงตอนเดียว และอยู่ในรูปแบบต่อไปนี้
I=>L=> O
แต่สำหรับอัลกอริทึมที่ซับซ้อนมากขึ้นจำเป็นต้องมีการวินิจฉัยตอนกลางหลาย ๆ ตอน คือ L1, L2, …, Ln ดังนั้น อัลกอริทึมหรือโปรแกรมจึงถูกแตกออกมาเป็นส่วน ๆ เรียกว่าเซ็กต์เม้นท์ (Segment)ซึ่งอาจเป็นประโยคคำสั่งเดีวบล็อกการวนลูป หรือทั้งโปรแกรม โด่ยแต่ละเซ็กต์เม้นท์จะมี Li หรือ I เป็นเงื่อนไขตอนต้นและมี Li+1 หรือ O เป็นเงื่อนไขตอนท้ายดังในรูปที่ 1
I=>L=> O
แต่สำหรับอัลกอริทึมที่ซับซ้อนมากขึ้นจำเป็นต้องมีการวินิจฉัยตอนกลางหลาย ๆ ตอน คือ L1, L2, …, Ln ดังนั้น อัลกอริทึมหรือโปรแกรมจึงถูกแตกออกมาเป็นส่วน ๆ เรียกว่าเซ็กต์เม้นท์ (Segment)ซึ่งอาจเป็นประโยคคำสั่งเดีวบล็อกการวนลูป หรือทั้งโปรแกรม โด่ยแต่ละเซ็กต์เม้นท์จะมี Li หรือ I เป็นเงื่อนไขตอนต้นและมี Li+1 หรือ O เป็นเงื่อนไขตอนท้ายดังในรูปที่ 1
รูปที่ 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) ในการตรวจสอบความถูกต้องจะใช้ค่าพารามิเตอร์ต่าง ๆ เป็นเงื่อนไขตอนต้น ค่าต่าง ๆ ที่ต้องส่งกลับคืนมาเป็นเงื่อนไขตอนท้าย และตัวฟังก์ชันเป็นการวินิจฉัยตอนกลาง
ดังนั้น ทางเลือกการเขียนโปรแกรมที่ดีจึงต้องมีการวางกฎเกณฑ์ในการวินิจฉัยและดำเนินการตรวจสอบตามแนวทางที่วางไว้ และถึงแม้ว่าไม่สามารถรับประกันว่าอัลกอริทึมจะทำงานถูกต้องอย่างสมบูรณ์ แก็ทำให้ผู้เขียนโปรแกรมมีความเข้าใจอัลกอริทึมมากขึ้นและเกิดความมั่นใจในการทำงานที่ถูกต้องหลังจากได้มีการตรวจสอบ
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 เพื่อหาค่าหารร่วมมาก ตัวเลขที่รับเข้ามานี้ค่าที่มากกว่าจะว่าจะถูกหารด้วยค่าที่ีน้อยกว่า
ตารางที่ 2 อัลกอริทึมของยูคลิด
อัลกอริทึมอื่น ๆ และของยูคลิดเป็นชุดการทำงานเพื่อใช้งานหรือแก้ไขปัญหาบางอย่างโดยการทำงานต้องมีขอบเขตที่สามารถไปถึงจุดสิ้นสุด (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
อัลกอริทึมของยูคลิดมีการทำงานที่ถึงจุดสิ้นสุด คือ ค่าที่เหลือเก็บไว้ที่ r น้อยกว่าค่าของ n และถ้าเริ่มต้นให้ n < m ในแต่ละรอบการวนลูปทั้งค่าของ m และ n จะถูกแทนด้วยค่าที่น้อยกว่าซึ่งค่าใหม่ของ m ยังคงมากกว่าค่าของ n จะน้อยลงเรื่อย ๆ จนเงื่อนไขที่ค่าของ r = 0 เป็นจริง ในกรณีโชคร้ายหรือแย่ที่สุดคือ ค่าของ n ลดลงเป็น 1 หากพบว่าเริ่มต้นค่าของ n > m จะมีการสลับค่ากันละหว่าง m กับ n โดยอัลกอริทึมของยูคลิดเขียนเป็นตัวอย่างโปรแกรมได้เป็นตารางที่ 8.3
ตารางที่ 3 การหาค่าหารร่วมมาก
ประสิทธิภาพการทำงานของอัลกอริทึม
ประสิทธิภาของอัลกอริทึมโดยทั่วไปมีมตรฐานการวัดผลสองแบบโดยแบบแรก คือ การใช้พื้นที่ว่าง (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)
2. ขนิดของเครื่องคอมพิวเตอร์ คำสั่ง (Instruction)และความเร็วของคอมพิวเตอร์มีผลต่อเวลาในการทำงาน ปัจจัยนี้ขึ้นกับเครื่องคอมิวเตอร์ที่นำมาใช้ ซึ่งไม่สามารถคาดคะเนให้ความหมายเวลา T(n)อยู่ในลักษณะของเวลาที่เป็นจริง(วินาที)แต่จะนับจำนวนของคำสั่งที่ใช้ในการทำงานโดยประมาณเป็นเวลาT(n )แทน
3. คุณภาะซอรสโค้ดและคอมไพเลอร์ เป็นอีกปัจจัยหนค่งที่มีผลต่อเวลาทีใช้ทำงานซึ่งขึ้นกับคุณภาพของซอร์สโคด้ (Source Code) ที่เขียนการทำงานเป็นอัลกอริทึมและคุณภาพของคอมไพเลอร์(Compiler)ในการแปลงซอร์สโค้ดไปเป็นโค้ดภาษาเครื่อง(Machine Code ) ในบางภาษาเขียนโปแกรมมีความเหมาะสมกว่าในการเขียนอัลกอริทึมในขณะที่บางภาษามีคอมไพเลอร์ที่แปลงงโค้ดได้ดีกว่า ซึ่งหมายความว่าค่า T(n)ไม่สามารถจะทราบได้เมื่อไช้กับการนับจำนวนของคำสั่งในการทำงาน(ข้อ 2)
ประสิทธิภาพกับขนาดข้อมูลที่รับเข้ามา
ตัวอย่างต่อไปนี้เป็นอัลกอริทคมที่ได้กล่าวมาแลวนารางที่ 1 เป็นการคำนวนหาค่าเฉลี่ยจากการรับค่าเข้ามา n ค่าที่เก็บไว้ในอาร์เรย์ และมีการกำหนดหมายเลขบรรทัดให้กับและประโยคเพื่อความสะดวกในการอ้างถึงได้เป็นดังในตารางที่ 4
ตารางที่ 4 อัลกอริทึมการคำนวนหาคาเฉลี่ย
ประโยคบรรทัด 1 และ 2 มีการนำงนเยงครั้งเดียว ประโยคบรรทัด 4 และ 5 ประกอบกันเป็นการทำงานแบบวนลูปมีการทำงาน n ครั้ง ประโยคบรรทัด 3 ซึ่งเป็นตัวควบคุมการทำงานซ้ำมีการทำงาน n+1ครั้ง เพิ่ม 1 เข้ามาเป็นการตรวจสอบเงื่อนไขในกรณีที่ตัวแปร iมีค่าไม่น้อยกว่า n หลังจากจบการวนลูปประโยคบรรทัด 6 มีการทำงานครั้งเดียว จากการวิเคราะห์ดังกล่าวได้เป็นตารางผลสรุปดังรูปที่ 2
รูปที่ 2 จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่ 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))
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) ? 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 และมีการกำหนดหมายเลขบรรทัดให้กับแต่ละประโยค
ตารางที่ 5 อัลกอริทึมการเรียงลำดับแบบเลือก
ประโยคบรรทัดที่ 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 ตามลำดับซึ่งจะได้เวลาในการทำงานของอัลกอริทึมเป็น ดังนี้
ในการวนลูปรอบที่ สองค่า 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) + n (n+1)/2-1+3(n(n-1))/2
=2n2+4n-5
เมื่อ n ? n2สำหรับทุก n ? 0จะได้ว่า
2n2 + 4n - 5 ? 2n2 + 4n = 6n2
=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
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) ซึ่งเริ่มต้นการค้นหาที่สมาชิกในตำแหน่งแรกของรายการและทดสอบกับสมาชิกในตำแหน่งถัดแรกของรายการและทดสอบกับสมาชิก ในตำแหน่งส่งถัดไปจนกว่าจะพบค่าที่ต้องการหรือสิ้นสุดการค้นหาที่ท้ายรายการได้เป็นอัลกอริทึมดันในตารางที่ 6
ประสิทธิภาพของอัลกอริทึมจึงขึ้นอยู่กับการจัดการกับข้อมูลอย่าไรโดยตัวอย่างที่นำมาแสดงให้ทราบความแตกต่างของ
แต่ละอัลกอริทึม ที่ใช้แก้ปัญหาแก้ปัญหาแบบเดียว ซึ่งเป็นการค้นหาค่าที่ต้องการมีอยู่ในอาร์เรย์ที่มีสมาชิก n ตัวหรือไม่ แบบแรกเป็นอัลกอริทึมแบบง่ายที่นำมาใช้ดำเนินการค้นหาเป็นการค้นหาตามลำดับเชิงเส้น (Linear Search) ซึ่งเริ่มต้นการค้นหาที่สมาชิกในตำแหน่งแรกของรายการและทดสอบกับสมาชิกในตำแหน่งถัดแรกของรายการและทดสอบกับสมาชิก ในตำแหน่งส่งถัดไปจนกว่าจะพบค่าที่ต้องการหรือสิ้นสุดการค้นหาที่ท้ายรายการได้เป็นอัลกอริทึมดันในตารางที่ 6
ตารางที่ 6 อับกอริทึมการค้นหาแบบเชิงเส้น
ในกรณีแย่ที่สุดของการค้นหาคือ ไม่พบค่าที่ต้องการมีอยู่ในรายการ ซึ่งใช้เวลาการทำงาน TL(n)สำหรับอัลกอริทึมการค้นหาแบบเชิงเส้นในรูที่ 3
รูปที่ 3 จำนวนการทำงานทั้งหมดของอัลกอริทึมในตารางที่ 6
เมื่อ TL(n) = 3n+3 จะได้ว่า
TL(n)=O(n)
และ 3n+3 ? 4nสำหรับทุก n ? 3
ถ้าหากรายการที่นำมาใช้ค้นหามีการจัดเรียงลำดับข้อมูลอยู่ก่อนแล้ว ก็สามารถใช้แบบที่ สองโดยอัลกอริทึมจะดำเนินการค้นหาแบบแบ่งครึ่ง (Binary Search)แทนการใช้แบบเชิงเส้นเป็นการค้นหาที่ต้องการโดยไปยังสมาชิกตรงกลางของรายการและทำการตรวจสอบค่าซึ่งมีความเป็นไปได้ 3 รูปแบบ คือ
1.ค่าที่ต้องการหาน้อยกว่าค่าของสมาชิกที่อยู่ตรงกลาง ค้นหาต่อในส่วนครึ่งแรกที่เหลือของรายการ
2.ค่าที่ต้องการหามากกว่าค่าของสมาชิดที่อยู่ตรงกลาง ค้นหาต่อในส่ายครึ่งท้ายี่เหลือของรายการ
3.ค่าที่ต้องการหาเท่ากับค่าของสมาลอกที่อยู่ตรงกลาง ค้นพบค่าที่ต้องการ
กระบวนการค้นหาจะทำไปเรื่อย ๆ จนกว่าจะพบค่าที่ต้องการหรือไม่พบเมือรายการย่อยที่ต้องค้นหาว่างเปล่าได้เป็นอัลกอริทึมดังในตารางที่ 7
และ 3n+3 ? 4nสำหรับทุก n ? 3
ถ้าหากรายการที่นำมาใช้ค้นหามีการจัดเรียงลำดับข้อมูลอยู่ก่อนแล้ว ก็สามารถใช้แบบที่ สองโดยอัลกอริทึมจะดำเนินการค้นหาแบบแบ่งครึ่ง (Binary Search)แทนการใช้แบบเชิงเส้นเป็นการค้นหาที่ต้องการโดยไปยังสมาชิกตรงกลางของรายการและทำการตรวจสอบค่าซึ่งมีความเป็นไปได้ 3 รูปแบบ คือ
1.ค่าที่ต้องการหาน้อยกว่าค่าของสมาชิกที่อยู่ตรงกลาง ค้นหาต่อในส่วนครึ่งแรกที่เหลือของรายการ
2.ค่าที่ต้องการหามากกว่าค่าของสมาชิดที่อยู่ตรงกลาง ค้นหาต่อในส่ายครึ่งท้ายี่เหลือของรายการ
3.ค่าที่ต้องการหาเท่ากับค่าของสมาลอกที่อยู่ตรงกลาง ค้นพบค่าที่ต้องการ
กระบวนการค้นหาจะทำไปเรื่อย ๆ จนกว่าจะพบค่าที่ต้องการหรือไม่พบเมือรายการย่อยที่ต้องค้นหาว่างเปล่าได้เป็นอัลกอริทึมดังในตารางที่ 7
ตารางที่ 8.7 อัลกอริทึมการค้นหาแบบแบ่งครึ่ง
จากอัลกอริทึมนี้จะเห็นว่าประโยคบรรทัด 1 , 2 และ 3 มีการทำงานเพียงครั้งเดียว การทำงานถัดไปใช้กับกรณีแย่ที่สุดในการทำนวณเวลา Ta(n) โดยพิจารณาจากจำนวณครั้งการทำงานวนลูปตั้งแต่ประโยคบรรทัด 4 จนถึง 10 ซึ่งในการทำงานแต่ละราบของการวนลูป ขนาดของรายการจะลดลงเหลือครึ่งหนึ่งไปเรื่อย ๆ
จนกว่าจะพบค่าที่ต้องการ นื่องจากใช้กรณีแย่ที่สุดจึงค้นหาถึงรอบท้ายสุดที่รายการเหลือเพียงค่าเดียว ดังนั้นจำนวนครั้งในการวนลูปกับบวกจำนวน k ราบของการนลูปจนกราการเหลือเพียงคาเดียว
เนื่องจากขนาดของรายการที่เหลืเพื่อใช้ค้นหาในเราบที่ได้ n/2k และต้องเป็น
จนกว่าจะพบค่าที่ต้องการ นื่องจากใช้กรณีแย่ที่สุดจึงค้นหาถึงรอบท้ายสุดที่รายการเหลือเพียงค่าเดียว ดังนั้นจำนวนครั้งในการวนลูปกับบวกจำนวน k ราบของการนลูปจนกราการเหลือเพียงคาเดียว
เนื่องจากขนาดของรายการที่เหลืเพื่อใช้ค้นหาในเราบที่ได้ n/2k และต้องเป็น
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
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
รูปที่ 4 จำนวนการทำงานอัลกอริทึมในยุคลิคในการณีที่แย่ที่สุดในแต่ละช่วง
ลักษณะเชิงซ้อนของอัลกอริทึม
การวัดผลประสิทธิภาพของอัลกอริทึมโดยใช้เวลาในการทำงานเพื่อให้งานสำเร็จเป็นการประมาณการของเวลาที่ต้องใช้ ซึ่งมีอยู่ 2 วิธี คือ นับการดำเนินการ (Operation Count) จะแยกแยะการดำเนินการของคำสั่งและนับจำนวนเวลาที่ใช้ดำเนินการนั้น อีกวิธีคือนับขั้นตอน (Step Count) จะนับจำนวนเวลาของขั้นตอนการทำงานทั้งหมดในโปรแกรม ดังในตัวอย่างที่ผ่านมาใช้วิธีนี้ ซึ่งเหตุผลสำคัญที่นำมาใช้เพื่อคาดการณ์ล่วงหน้าถึงการเติบโตของเวลาที่ใช้ปัญหางานแบบเดียวกัน โดยมีเครื่องหมายที่นำมาใช้ 3 ลักษณะ คือ
1. เครื่องหมายบิ๊กโอ (Big Oh Notation, O) แสดงเป็น f (n) = O (g (n)) หมายความว่าเวลาการทำงานของ f (n) น้อยกว่าหรือเท่ากับ g (n) และได้ว่า g (n) เป็นขอบเขตด้านบนของ f (n)
2. เครื่องหมายโอเมก้า (Omega Notation, ? ) แสดงเป็น f (n) = ? (g (n)) หมายความว่าเวลาการทำงานของ f (n) และได้ว่า g (n) เป็นขอบเขตด้านล่างของ f (n)
3. เครื่องหมายเตตตะ (Theta Notation,) แสดงเป็น 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 เป็นบิ๊กโอของ g ถ้ามีค่าคงที่ c เป็นบวกและ f ไม่มากกว่า cg สำหรับค่าใด ๆ คือ n0 โดยทุก ๆ n0 ต้องไม่มากกว่า N จากความสัมพันธ์ของ f กับ g แสดงให้เห็นว่า g(n) เป็นขอบเขตด้านบนของ f (n) หรือ g (n) ใช้เวลาในการทำงานนานกว่า f (n) หรือ f (n) เติบโตจนทำงานเร็วเท่า g (n) และจัดให้อยู่ในรูปแบบเรียบง่ายในลักษณะของ n ที่คูณกับค่าค่งที่ c = 1 การแบ่งขอบเขตด้านบนจะได้เป็นลักษณะเชิงซ้อนที่ไม่สิ้นสุดโดยมีขอบเขตหลัก ๆ ดังนี้
ฟังก์ชันเชิงเส้น (Linear Function)
พิจารณา f (n) = 3n+2 เมื่อ n มีค่าอย่างน้อย 2 จะได้ 3n+2 ? 3n+n ? 4n ดังนั้น f (n) = O(n) จะมีขอบเขตด้านบนเป็นฟังก์ชันเชิงเส้น หรือ f (n) = 100n+6 ? 100n+n=101n เมื่อ n ? 6 จะได้ 100+6 = O(n) เช่นกัน
ฟังก์ชันยกกำลังสอง (Quadratic Function)
พิจารณา f (n) = 10 n^2 +4 n+2 เมื่อ n ? 2 จะได้ f (n) ? 10 n^2 +5 n และให้ n ? 5, 5n ? n^2 ดังนั้น f (n) ? 10 n^ 2+ n^ 2 = 11n^2 ก็จะได้ว่า f (n) = O(n^2) หรือ f (n) = 1000n^2 +100n-6 จะได้ f (n) ? 1000 n^2+100n สำหรับทุก n และได้ว่า 100n ? n^2 เมื่อ n ? 100 ดังนั้น f (n) ? 1001 n^2 และ f (n) = O(n^2)
หากมีการใช้ n หลายที่และต้องทำให้เป็นเครื่องหมายบิ๊กโอต้องแยกเป็นแต่ละหน่วย (Unit Term) จากตัวอย่าง 10n^2+4n+2 เมื่อแยกออกมาได้เป็น n^2, n และ 1 จากนั้นใช้หน่วยที่มากที่สุดเป็นลักษณะเชิงซ้อนในที่นี้ คือ n^2
ฟังก์ชันเอ็กโปเนนเซียล (Exponential Function)
พิจารณา f (n) = 6*2^n+n^2 จะเห็นว่าเมื่อ n ? 4, n^2 ? 2^n จะได้ f (n) ? 6*2 ^n + n^2 = 7*2^n ดังนั้น 6*2^n+n^2 = O(2^n)
พิจารณา f (n) = 3n+2 เมื่อ n มีค่าอย่างน้อย 2 จะได้ 3n+2 ? 3n+n ? 4n ดังนั้น f (n) = O(n) จะมีขอบเขตด้านบนเป็นฟังก์ชันเชิงเส้น หรือ f (n) = 100n+6 ? 100n+n=101n เมื่อ n ? 6 จะได้ 100+6 = O(n) เช่นกัน
ฟังก์ชันยกกำลังสอง (Quadratic Function)
พิจารณา f (n) = 10 n^2 +4 n+2 เมื่อ n ? 2 จะได้ f (n) ? 10 n^2 +5 n และให้ n ? 5, 5n ? n^2 ดังนั้น f (n) ? 10 n^ 2+ n^ 2 = 11n^2 ก็จะได้ว่า f (n) = O(n^2) หรือ f (n) = 1000n^2 +100n-6 จะได้ f (n) ? 1000 n^2+100n สำหรับทุก n และได้ว่า 100n ? n^2 เมื่อ n ? 100 ดังนั้น f (n) ? 1001 n^2 และ f (n) = O(n^2)
หากมีการใช้ n หลายที่และต้องทำให้เป็นเครื่องหมายบิ๊กโอต้องแยกเป็นแต่ละหน่วย (Unit Term) จากตัวอย่าง 10n^2+4n+2 เมื่อแยกออกมาได้เป็น n^2, n และ 1 จากนั้นใช้หน่วยที่มากที่สุดเป็นลักษณะเชิงซ้อนในที่นี้ คือ n^2
ฟังก์ชันเอ็กโปเนนเซียล (Exponential Function)
พิจารณา f (n) = 6*2^n+n^2 จะเห็นว่าเมื่อ n ? 4, n^2 ? 2^n จะได้ f (n) ? 6*2 ^n + n^2 = 7*2^n ดังนั้น 6*2^n+n^2 = O(2^n)
ฟังก์ชันคงที่ (Constant Function)
เมื่อ f (n) = 9 หรือ f (n) = 2033 จะเขียนเป็น f (n) = O(1) ซึ่งมีความถูกต้องโดยพิจารณาจาก f (n) = 9 ? 9*1 กำหนดให้ c = 9 และ n = 1 เป็นไปตามข้อกำหนดของบิ๊กโอ หรือ f (n) = 2033 ? 2033*1 ก็เป็นไปตามข้อกำหนดของบิ๊กโอโดยให้ c = 2033 และ n-1
จะเห็นว่าเวลาทำงานในลักษณะเชิงซ้อนของโปรแกรมมีรูปแบบของบางฟังก์ชันที่ใช้เป็นลักษณะตัวอย่าง และฟังก์ชันเหล่านี้นำมาใช้พิจารณาเวลาที่ต้องการเมื่อตัวอย่างมีการเปลี่ยนแปลง นอกจากนี้ ฟังก์ชันลักษณะเชิงซ้อนยังใช้กับการเปรียบเทียบโปรแกรม P และ Q ที่ดำเนินการแก้ปัญหางานแบบเดียวกัน สมมุติให้โปรแกรม P มีเวลาเชิงซ้อนเป็น O(n^2) และโปรแกรม Q มีเวลาเชิงซ้อนเป็น O(n) จะเห็นว่าเวลาของโปรแกรม P ถูกกำหนดขอบเขตด้านบนด้วย cn โดย c เป็นค่าคงที่และทุก ๆ n ที่ n ? n1 ขณะโปรแกรม P ถูกกำหนดขอบเขตด้านล่างด้วย dn^2 สำหรับค่าคงที่ d และทุก ๆ n ที่ n ? n2 เมื่อ cn ? dn^2 สำหรับ n ? c/d จะได้ว่าโปรแกรม P ใช้เวลาทำงานเร็วกว่าโปรแกรม Q เมื่อ n ? max{n1,n2,c/d}
นอกจากนี้ขนาดของ n ของทั้งสองโปรแกรมต้องมากพอจึงทำให้โปรแกรม P ทำงานเร็วกว่าโปรแกรม Q ดังนั้นจะต้องทราบค่า m ที่มากพอ ถ้าโปรแกรม P ทำงาน 10 ^6n หนึ่งในพันวินาที (Millisecond) และโปรแกรม Q ทำงาน n^2 หนึ่งในพันวินาที ถ้าหากให้ n ? 10 ^6 ก็เลือกใช้โปรแกรม Q ทำงานดีกว่า
เพื่อให้ทราบและเข้าใจการเติบโตของฟังก์ชันกับค่า n ที่หลากหลายเป็นอย่างไรโดยมีรูปภาพประกอบคือ รูปที่ 8.5 จากรูปดังกล่าวแสดงให้เห็นว่า 2^n มีการเติบโตที่รวดเร็วมากเมื่อเทียบกับค่า n ที่เพิ่มขึ้น ถ้าให้โปรแกรมใช้ 2^n ขั้นตอนในการทำงาน เมื่อ n = 40 จำนวนขั้นตอนที่ต้องใช้ประมาณ 1.1*10 ^12 หากทำงานบนคอมพิวเตอร์ที่ดำเนินการ 1,000,000,000 ขั้นตอนต่อวินาที โปรแกรมนี้ต้องใช้เวลาทำงานประมาณ 18.3 นาที ถ้าให้ n = 50 โปรแกรมนี้ต้องใช้เวลาถึง 13 วัน ถ้าให้ n = 60 จะใช้เวลา 310.56 ปีเพื่อทำงานโปรแกรมนี้ให้เสร็จ จึงสรุปได้ว่าประโยชน์ของโปรแกรมที่จะได้รับกับลักษณะเชิงซ้อนแบบเอ็กโปเนนเชียลถูกจำกัดด้วยค่า n ที่มีจำนวนน้อย ๆ (n ? 40)
เมื่อ f (n) = 9 หรือ f (n) = 2033 จะเขียนเป็น f (n) = O(1) ซึ่งมีความถูกต้องโดยพิจารณาจาก f (n) = 9 ? 9*1 กำหนดให้ c = 9 และ n = 1 เป็นไปตามข้อกำหนดของบิ๊กโอ หรือ f (n) = 2033 ? 2033*1 ก็เป็นไปตามข้อกำหนดของบิ๊กโอโดยให้ c = 2033 และ n-1
จะเห็นว่าเวลาทำงานในลักษณะเชิงซ้อนของโปรแกรมมีรูปแบบของบางฟังก์ชันที่ใช้เป็นลักษณะตัวอย่าง และฟังก์ชันเหล่านี้นำมาใช้พิจารณาเวลาที่ต้องการเมื่อตัวอย่างมีการเปลี่ยนแปลง นอกจากนี้ ฟังก์ชันลักษณะเชิงซ้อนยังใช้กับการเปรียบเทียบโปรแกรม P และ Q ที่ดำเนินการแก้ปัญหางานแบบเดียวกัน สมมุติให้โปรแกรม P มีเวลาเชิงซ้อนเป็น O(n^2) และโปรแกรม Q มีเวลาเชิงซ้อนเป็น O(n) จะเห็นว่าเวลาของโปรแกรม P ถูกกำหนดขอบเขตด้านบนด้วย cn โดย c เป็นค่าคงที่และทุก ๆ n ที่ n ? n1 ขณะโปรแกรม P ถูกกำหนดขอบเขตด้านล่างด้วย dn^2 สำหรับค่าคงที่ d และทุก ๆ n ที่ n ? n2 เมื่อ cn ? dn^2 สำหรับ n ? c/d จะได้ว่าโปรแกรม P ใช้เวลาทำงานเร็วกว่าโปรแกรม Q เมื่อ n ? max{n1,n2,c/d}
นอกจากนี้ขนาดของ n ของทั้งสองโปรแกรมต้องมากพอจึงทำให้โปรแกรม P ทำงานเร็วกว่าโปรแกรม Q ดังนั้นจะต้องทราบค่า m ที่มากพอ ถ้าโปรแกรม P ทำงาน 10 ^6n หนึ่งในพันวินาที (Millisecond) และโปรแกรม Q ทำงาน n^2 หนึ่งในพันวินาที ถ้าหากให้ n ? 10 ^6 ก็เลือกใช้โปรแกรม Q ทำงานดีกว่า
เพื่อให้ทราบและเข้าใจการเติบโตของฟังก์ชันกับค่า n ที่หลากหลายเป็นอย่างไรโดยมีรูปภาพประกอบคือ รูปที่ 8.5 จากรูปดังกล่าวแสดงให้เห็นว่า 2^n มีการเติบโตที่รวดเร็วมากเมื่อเทียบกับค่า n ที่เพิ่มขึ้น ถ้าให้โปรแกรมใช้ 2^n ขั้นตอนในการทำงาน เมื่อ n = 40 จำนวนขั้นตอนที่ต้องใช้ประมาณ 1.1*10 ^12 หากทำงานบนคอมพิวเตอร์ที่ดำเนินการ 1,000,000,000 ขั้นตอนต่อวินาที โปรแกรมนี้ต้องใช้เวลาทำงานประมาณ 18.3 นาที ถ้าให้ n = 50 โปรแกรมนี้ต้องใช้เวลาถึง 13 วัน ถ้าให้ n = 60 จะใช้เวลา 310.56 ปีเพื่อทำงานโปรแกรมนี้ให้เสร็จ จึงสรุปได้ว่าประโยชน์ของโปรแกรมที่จะได้รับกับลักษณะเชิงซ้อนแบบเอ็กโปเนนเชียลถูกจำกัดด้วยค่า n ที่มีจำนวนน้อย ๆ (n ? 40)
รูปที่ 5 ค่าต่างๆ ของฟังก์ชันในลักษณะเชิงซ้อน
เช่นกันหากโปรแกรมมีลักษณะเชิงซ้อนแบบโพลิโนเมียล (Polynomial) ที่มีดีกรีสูงก็จะถูกจำกัดประโยชน์ที่ได้ เช่น ให้โปรแกรมต้องการใช้ n^10 ขั้นตอนการทำงานบนคอมพิวเตอร์ที่ดำเนินการ 1,000,000,000 ขั้นตอนต่อวินาที โปรแกรมนี้ต้องใช้เวลา 10 วินาทีเมื่อ n = 10 ใช้เวลา 3171 ปี เมื่อ n = 100 และใช้เวลา 3.17*10 ^13 ปี เมื่อ n = 1000 แต่ถ้าลักษณะเชิงซ้อนของโปรแกรมเป็น n^3 ขั้นตอน คอมพิวเตอร์ต้องการใช้เวลา 1 วินาที เมื่อ n = 1000 ใช้เวลา 110.67 นาที เมื่อ n = 10,000 และใช้เวลา 11.57 วัน เมื่อ n = 100,000
ไม่มีความคิดเห็น:
แสดงความคิดเห็น