อัลกอริทึม

 อัลกอริทึม

       ขั้นตอนวิธี หรือ อัลกอริทึม (อังกฤษ: algorithm) หมาย ถึงกระบวนการแก้ปัญหาที่สามารถเข้าใจได้ มีลำดับหรือวิธีการในการแก้ไขปัญหาใดปัญหาหนึ่งอย่างเป็นขั้นเป็นตอนและ ชัดเจน เมื่อนำเข้าอะไร แล้วจะต้องได้ผลลัพธ์เช่นไร ซึ่งแตกต่างจากการแก้ปัญหาแบบสามัญสำนึก หรือฮิวริสติก (heuristic)

โดยทั่วไป ขั้นตอนวิธี จะประกอบด้วย วิธีการเป็นขั้นๆ และมีส่วนที่ต้องทำแบบวนซ้ำ (iterate) หรือ เวียนเกิด (recursive) โดยใช้ตรรกะ (logic) และ/หรือ ในการเปรียบเทียบ (comparison) ในขั้นตอนต่างๆ จนกระทั่งเสร็จสิ้นการทำงาน

ในการทำงานอย่างเดียว กัน เราอาจจะเลือกขั้นตอนวิธีที่ต่างกันเพื่อแก้ปัญหาได้ โดยที่ผลลัพธ์ที่ได้ในขั้นสุดท้ายจะออกมาเหมือนกันหรือไม่ก็ได้ และจะมีความแตกต่าง ที่จำนวนและชุดคำสั่งที่ใช้ต่างกันซึ่งส่งผลให้ เวลา (time) , และขนาดหน่วยความจำ (space) ที่ต้องการต่างกัน หรือเรียกได้อีกอย่างว่ามีความซับซ้อน (complexity) ต่างกัน

การนำขั้นตอนวิธีไปใช้ ไม่จำกัดเฉพาะการเขียนโปรแกรมคอมพิวเตอร์ แต่สามารถใช้กับปัญหาอื่น ๆ ได้เช่น การออกแบบวงจรไฟฟ้า, การทำงานเครื่องจักรกล, หรือแม้กระทั่งปัญหาในธรรมชาติ เช่น วิธีของสมองมนุษย์ในการคิดเลข หรือวิธีการขนอาหารของแมลง

หนึ่งในขั้นตอนวิธี อย่างง่าย คือ ขั้นตอนวิธีที่ใช้หาจำนวนที่มีค่ามากที่สุดในรายการ (ซึ่งไม่ได้เรียงลำดับไว้) ในการแก้ปัญหานี้ เราจะต้องดูจำนวนทุกจำนวนในรายการ ซึ่งมีขั้นตอนวิธีดังนี้

1.    ดูแต่ละจำนวนในรายการ ถ้ามันมีค่ามากกว่า จำนวนที่มีค่ามากที่สุดที่เราเคยพบจดค่ามันไว้

2.   จำนวนที่เราจดไว้ตัวสุดท้าย จะเป็นจำนวนที่มีค่ามากที่สุด

และนี่คือรหัสเทียมสำหรับขั้นตอนวิธีนี้

Algorithm LargestNumber   Output: จำนวนเต็มที่มีค่ามากที่สุดในรายการ.
  Input: รายการจำนวนเต็ม.
  largest ← -∞
  for each item in รายการ, do
    if the item > largest, then
      largest ← the item
  return largest

            การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบท ที่  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