ในวิทยาการคอมพิวเตอร์ประสิทธิภาพของอัลกอริทึมเป็นคุณสมบัติของอัลกอริทึมที่เกี่ยวข้องกับปริมาณทรัพยากรการคำนวณที่อัลกอริทึมใช้ ประสิทธิภาพของอัลกอริทึมอาจเปรียบได้กับประสิทธิภาพการผลิต ทางวิศวกรรม สำหรับกระบวนการที่ทำซ้ำหรือต่อเนื่อง

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

ตัวอย่างเช่นCycle SortและTimSortต่างก็เป็นอัลกอริธึมที่ใช้เรียงลำดับรายการจากน้อยไปมาก Cycle Sort จะจัดเรียงรายการโดยใช้เวลาแปรผันตามจำนวนองค์ประกอบยกกำลังสอง (${\textstyle O(n^{2})}$(ดูสัญกรณ์ Big O ) แต่ลดการเขียนลงในอาร์เรย์เดิมให้น้อยที่สุด และต้องการ หน่วยความจำเพิ่มเติมเพียงเล็กน้อยซึ่งคงที่เมื่อเทียบกับความยาวของรายการ (${\textstyle O(1)}$). Timsort เรียงลำดับรายการตามเวลาแบบลิเนียร์ลิมิทึม (แปรผันตามปริมาณคูณด้วยลอการิทึมของปริมาณนั้น) ตามความยาวของรายการ (${\textstyle O(n\log n)}$) แต่มีความต้องการพื้นที่เชิงเส้นตามความยาวของรายการ (${\textstyle O(n)}$ถ้าหากจำเป็นต้องเรียงลำดับรายการขนาดใหญ่ด้วยความเร็วสูงสำหรับแอปพลิเคชันใดแอปพลิเคชันหนึ่ง timsort จะเป็นตัวเลือกที่ดีกว่า อย่างไรก็ตาม หากการลดรอบการเขียนโปรแกรม/ลบ และการใช้หน่วยความจำของการเรียงลำดับมีความสำคัญมากกว่า cycle sort จะเป็นตัวเลือกที่ดีกว่า

เอดา โลฟเลซได้เน้นย้ำถึงความสำคัญของประสิทธิภาพในแง่ของเวลาในปี ค.ศ. 1843 โดยนำไปประยุกต์ใช้กับเครื่องวิเคราะห์เชิงกลของชาร์ลส์ แบ็บเบจ :

"ในการคำนวณเกือบทุกครั้ง มีความเป็นไปได้มากมายในการจัดเรียงลำดับของกระบวนการ และต้องพิจารณาปัจจัยต่างๆ หลายประการในการเลือกการจัดเรียงเหล่านั้นเพื่อวัตถุประสงค์ของเครื่องจักรคำนวณ วัตถุประสงค์ที่สำคัญประการหนึ่งคือการเลือกการจัดเรียงที่มีแนวโน้มที่จะลดเวลาที่จำเป็นในการคำนวณให้น้อยที่สุด" ^{[ 1 ]}

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

คอมพิวเตอร์สมัยใหม่เร็วกว่าคอมพิวเตอร์รุ่นแรกๆ อย่างมาก และมีหน่วยความจำให้ใช้งานมากกว่าเดิม ( กิกะไบต์ แทนที่จะเป็นกิโลไบต์ ) อย่างไรก็ตามโดนัลด์ คนูธเน้นย้ำว่าประสิทธิภาพยังคงเป็นสิ่งสำคัญที่ต้องพิจารณา:

"ในสาขาวิศวกรรมที่ได้รับการยอมรับ การปรับปรุง 12% ซึ่งทำได้ง่ายนั้นไม่เคยถูกมองว่าเป็นเรื่องเล็กน้อย และฉันเชื่อว่ามุมมองเดียวกันนี้ควรนำมาใช้ในวิศวกรรมซอฟต์แวร์" ^{[ 2 ]}

ในยุคของAIแม้ว่า LLM จะสามารถสร้างโค้ดที่ใช้งานได้ แต่โค้ดเหล่านี้มักจะไม่ตรงตาม มาตรฐาน ประสิทธิภาพที่จำเป็นในแอปพลิเคชันที่มีทรัพยากรจำกัดหรือคำนึงถึงเวลา^{[ 3 ]}ทำให้ประสิทธิภาพของโค้ดกลายเป็นปัญหาคอขวดที่สำคัญสำหรับการใช้งานจริง

อัลกอริทึมจะถือว่ามีประสิทธิภาพหากการใช้ทรัพยากร หรือที่เรียกว่าต้นทุนการคำนวณ อยู่ในระดับที่ยอมรับได้หรือต่ำกว่านั้น โดยทั่วไปแล้ว 'ยอมรับได้' หมายความว่า อัลกอริทึมจะทำงานได้ในเวลาหรือพื้นที่ที่เหมาะสมบนคอมพิวเตอร์ที่มีอยู่ โดยปกติแล้วจะขึ้นอยู่กับขนาดของข้อมูลป้อนเข้า นับตั้งแต่ทศวรรษ 1950 คอมพิวเตอร์มีการเพิ่มขึ้นอย่างมากทั้งในด้านกำลังการคำนวณและปริมาณหน่วยความจำ ดังนั้นระดับที่ยอมรับได้ในปัจจุบันจึงอาจไม่เป็นที่ยอมรับเมื่อ 10 ปีที่แล้วด้วยซ้ำ ในความเป็นจริง ด้วยกำลังการประมวลผลของคอมพิวเตอร์ที่เพิ่มขึ้นเป็นสองเท่าโดยประมาณทุกๆ 2 ปีงานที่ทำได้อย่างมีประสิทธิภาพในระดับที่ยอมรับได้บนสมาร์ทโฟนและระบบฝังตัว ในปัจจุบัน อาจไม่มีประสิทธิภาพในระดับที่ยอมรับไม่ได้สำหรับเซิร์ฟเวอร์ อุตสาหกรรม เมื่อ 10 ปีที่แล้ว

ผู้ผลิตคอมพิวเตอร์มักออกรุ่นใหม่ๆ อยู่เสมอ ซึ่งมักมีประสิทธิภาพ สูงขึ้น ค่าใช้จ่ายด้านซอฟต์แวร์อาจค่อนข้างสูง ดังนั้นในบางกรณี วิธีที่ง่ายและประหยัดที่สุดในการเพิ่มประสิทธิภาพอาจเป็นการซื้อคอมพิวเตอร์ที่เร็วขึ้นโดยตรง โดยมีเงื่อนไขว่าต้องสามารถใช้งานร่วมกับคอมพิวเตอร์เครื่องเดิมได้

มีหลายวิธีในการวัดทรัพยากรที่ใช้โดยอัลกอริทึม: สองวิธีที่พบมากที่สุดคือความเร็วและการใช้หน่วยความจำ วิธีอื่นๆ อาจรวมถึงความเร็วในการส่งข้อมูล การใช้ดิสก์ชั่วคราว การใช้ดิสก์ระยะยาว การใช้พลังงาน ต้นทุนรวมในการเป็นเจ้าของเวลาตอบสนองต่อสิ่งเร้าภายนอก เป็นต้น การวัดเหล่านี้หลายอย่างขึ้นอยู่กับขนาดของข้อมูลป้อนเข้าอัลกอริทึม กล่าวคือปริมาณข้อมูลที่จะต้องประมวลผล นอกจากนี้ยังอาจขึ้นอยู่กับวิธีการจัดเรียงข้อมูลด้วย ตัวอย่างเช่นอัลกอริทึมการเรียงลำดับ บางตัว ทำงานได้ไม่ดีกับข้อมูลที่เรียงลำดับแล้ว หรือข้อมูลที่เรียงลำดับย้อนกลับ

ในทางปฏิบัติ มีปัจจัยอื่นๆ ที่อาจส่งผลต่อประสิทธิภาพของอัลกอริทึม เช่น ข้อกำหนดด้านความแม่นยำและ/หรือความน่าเชื่อถือ ดังที่ได้อธิบายไว้ด้านล่าง วิธีการนำอัลกอริทึมไปใช้งานก็มีผลอย่างมากต่อประสิทธิภาพที่แท้จริงเช่นกัน แม้ว่าหลายแง่มุมในเรื่องนี้เกี่ยวข้องกับประเด็นการปรับให้เหมาะสม ที่สุดก็ตาม

การวิเคราะห์เชิงทฤษฎี

ในการวิเคราะห์เชิงทฤษฎีของอัลกอริทึมวิธีปฏิบัติทั่วไปคือการประมาณความซับซ้อนในเชิงอะซิมโทติก สัญลักษณ์ที่ใช้กันมากที่สุดในการอธิบายการใช้ทรัพยากรหรือ "ความซับซ้อน" คือสัญลักษณ์ Big OของDonald Knuthซึ่งแสดงถึงความซับซ้อนของอัลกอริทึมเป็นฟังก์ชันของขนาดของข้อมูลป้อนเข้า${\textstyle n}$สัญกรณ์ Big O เป็นการ วัดความ ซับซ้อนของฟังก์ชันเชิงอะซิมโทติก โดยที่${\textstyle f(n)=O{\bigl (}g(n){\bigr )}}$หมายความว่าโดยประมาณแล้ว ระยะเวลาที่ใช้ในการประมวลผลอัลกอริทึมจะแปรผันตรงกับ${\displaystyle g(n)}$โดยละเว้นพจน์ลำดับต่ำกว่าที่มีส่วนร่วมน้อยกว่า${\displaystyle g(n)}$เพื่อการเติบโตของฟังก์ชันดังกล่าว${\textstyle n}$มีขนาดใหญ่ขึ้นอย่างไม่มีกำหนดการประมาณค่านี้อาจทำให้เข้าใจผิดได้เมื่อ${\textstyle n}$มีขนาดเล็ก แต่โดยทั่วไปแล้วมีความแม่นยำเพียงพอเมื่อ${\textstyle n}$มีขนาดใหญ่เนื่องจากสัญลักษณ์เป็นแบบเชิงเส้นกำกับ ตัวอย่างเช่น การเรียงลำดับแบบบับเบิลอาจเร็วกว่าการเรียงลำดับแบบผสานเมื่อมีรายการที่ต้องเรียงลำดับเพียงไม่กี่รายการ อย่างไรก็ตาม การใช้งานทั้งสองแบบน่าจะตรงตามข้อกำหนดด้านประสิทธิภาพสำหรับรายการขนาดเล็ก โดยทั่วไปแล้ว โปรแกรมเมอร์สนใจอัลกอริทึมที่สามารถปรับขนาดได้อย่างมีประสิทธิภาพสำหรับขนาดอินพุตขนาดใหญ่ และการเรียงลำดับแบบผสานเป็นที่นิยมมากกว่าการเรียงลำดับแบบบับเบิลสำหรับรายการที่มีความยาวที่พบในโปรแกรมที่เน้นข้อมูลจำนวนมาก

ตัวอย่างบางส่วนของการใช้สัญกรณ์ Big O กับความซับซ้อนของเวลาเชิงอะซิมโทติกของอัลกอริทึม ได้แก่:

สัญกรณ์	ชื่อ	ตัวอย่าง
${\displaystyle O(1)}$	คงที่	การหาค่ามัธยฐานจากรายการค่าที่เรียงลำดับแล้ว การใช้ตารางค้นหาที่ มีขนาดคงที่ การใช้ ฟังก์ชันแฮชที่เหมาะสมสำหรับการค้นหารายการ
${\displaystyle O(\log n)}$	ลอการิทึม	การค้นหารายการในอาร์เรย์ที่เรียงลำดับแล้วโดยใช้การค้นหาแบบไบนารี หรือ ต้นไม้ค้นหาแบบสมดุลตลอดจนการดำเนินการทั้งหมดในฮีปแบบไบโนเมียล
${\displaystyle O(n)}$	เชิงเส้น	การค้นหารายการในรายการที่ไม่เรียงลำดับหรือโครงสร้างต้นไม้ที่ผิดรูป (กรณีที่เลวร้ายที่สุด) หรือในอาร์เรย์ที่ไม่เรียงลำดับ การบวก จำนวนเต็ม nบิตสองจำนวนโดยใช้การทดแบบระลอกคลื่น
${\displaystyle O(n\log n)}$	แบบเชิงเส้น แบบลอการิทึมเชิงเส้น หรือแบบกึ่งเชิงเส้น	การแปลงฟูริเยร์แบบเร็ว (Fast Fourier Transform ); การ เรียงลำดับแบบฮีปซอร์ ต (heapsort) , การเรียงลำดับแบบ ควิกซอร์ต (quicksort ) ( กรณีที่ดีที่สุดและกรณีเฉลี่ย ) หรือการเรียงลำดับแบบผสาน (merge sort)
${\displaystyle O(n^{2})}$	กำลังสอง	การคูณ เลข สอง จำนวนที่มี nหลักด้วยอัลกอริทึมแบบง่ายๆเช่นบับเบิลซอร์ต (กรณีที่เลวร้ายที่สุดหรือการใช้งานแบบง่ายๆ), เชลล์ซอร์ต , ควิกซอร์ต ( กรณีที่เลวร้ายที่สุด ), ซีเล็คชั่นซอร์ตหรืออินเสิร์ชชั่นซอร์ต
${\displaystyle O(c^{n}),\;c>1}$	เลขชี้กำลัง	การหาคำตอบที่เหมาะสมที่สุด (ไม่ใช่คำตอบโดยประมาณ ) สำหรับปัญหาพนักงานขายเดินทางโดยใช้การเขียนโปรแกรมเชิงพลวัต การ ตรวจสอบ ว่าข้อความตรรกะสองข้อความนั้นเทียบเท่ากันหรือไม่โดยใช้การค้นหาแบบบรูทฟอร์ซ

โดยปกติแล้ว ค่าที่วัดได้จะแสดงออกมาในรูปของฟังก์ชันของขนาดของข้อมูลป้อนเข้า${\displaystyle \scriptstyle {n}}$.

มาตรการที่ใช้กันทั่วไปสองอย่างคือ:

• เวลา : อัลกอริทึมนี้ใช้เวลานานเท่าใดจึงจะเสร็จสมบูรณ์?
• พื้นที่ : อัลกอริทึมต้องการหน่วยความจำในการทำงาน (โดยทั่วไปคือ RAM) เท่าใด? ซึ่งประกอบด้วยสองส่วน คือ ปริมาณหน่วยความจำที่โค้ดต้องการ (การใช้พื้นที่เสริม) และปริมาณหน่วยความจำที่จำเป็นสำหรับข้อมูลที่โค้ดประมวลผล (การใช้พื้นที่ภายใน)

สำหรับคอมพิวเตอร์ที่ใช้พลังงานจากแบตเตอรี่ (เช่นแล็ปท็อปและสมาร์ทโฟน ) หรือสำหรับการคำนวณที่ยาวนาน/ขนาดใหญ่มาก (เช่นซูเปอร์คอมพิวเตอร์ ) มาตรวัดอื่นๆ ที่น่าสนใจ ได้แก่:

• การใช้พลังงานโดยตรง : พลังงานที่จำเป็นโดยตรงในการใช้งานคอมพิวเตอร์
• การใช้พลังงานทางอ้อม : พลังงานที่จำเป็นสำหรับการทำความเย็น การให้แสงสว่าง เป็นต้น

ข้อมูล ณ ปี 2018การใช้พลังงานกำลังกลายเป็นตัวชี้วัดที่สำคัญมากขึ้นสำหรับงานคำนวณทุกประเภทและทุกขนาด ตั้งแต่อุปกรณ์Internet of Things (IoT) แบบฝังตัว ไปจนถึง อุปกรณ์System-on-Chip และ ศูนย์ ข้อมูลขนาดใหญ่ แนวโน้มนี้มักถูกเรียกว่า การคำนวณที่เป็นมิตร ต่อสิ่งแวดล้อม (Green Computing )

มาตรวัดประสิทธิภาพการคำนวณที่ไม่ค่อยพบเห็นทั่วไป อาจมีความเกี่ยวข้องในบางกรณีเช่นกัน:

• ขนาดการส่งข้อมูล : แบนด์วิดท์อาจเป็นปัจจัยจำกัดการบีบอัดข้อมูลสามารถใช้เพื่อลดปริมาณข้อมูลที่จะส่ง การแสดงภาพหรือรูปภาพ (เช่นโลโก้ Google ) อาจส่งผลให้มีการส่งข้อมูลหลายหมื่นไบต์ (48K ในกรณีนี้) เมื่อเทียบกับการส่งข้อมูลเพียงหกไบต์สำหรับข้อความ "Google" ซึ่งมีความสำคัญสำหรับ งาน ประมวลผลที่เน้นการรับส่งข้อมูล (I/O bound computing tasks)
• พื้นที่ภายนอก : พื้นที่ที่จำเป็นบนดิสก์หรืออุปกรณ์หน่วยความจำภายนอกอื่นๆ ซึ่งอาจใช้สำหรับการจัดเก็บชั่วคราวในขณะที่กำลังดำเนินการตามอัลกอริทึม หรืออาจเป็นการจัดเก็บระยะยาวที่จำเป็นสำหรับการอ้างอิงในอนาคต
• เวลาตอบสนอง ( ความหน่วง ): สิ่งนี้มีความสำคัญอย่างยิ่งในแอปพลิเคชันแบบเรียลไทม์เมื่อระบบคอมพิวเตอร์ต้องตอบสนองต่อเหตุการณ์ภายนอกอย่างรวดเร็ว
• ต้นทุนรวมในการเป็นเจ้าของ : โดยเฉพาะอย่างยิ่งหากคอมพิวเตอร์เครื่องนั้นถูกใช้เฉพาะกับอัลกอริทึมใดอัลกอริทึมหนึ่งโดยเฉพาะ

• การวิเคราะห์อัลกอริทึม — วิธีการกำหนดทรัพยากรที่จำเป็นสำหรับอัลกอริทึม
• เกณฑ์มาตรฐาน — วิธีการวัดเวลาและพื้นที่การประมวลผลเปรียบเทียบในกรณีที่กำหนด^{[ 10 ] [ 11 ] [ 12 ]}
• กรณีที่ดีที่สุด แย่ที่สุด และเฉลี่ย — ข้อควรพิจารณาในการประมาณเวลาในการดำเนินการในสามสถานการณ์
• การปรับแต่งประสิทธิภาพของคอมไพเลอร์ — การปรับแต่งประสิทธิภาพที่ได้มาจากคอมไพเลอร์
• ทฤษฎีความซับซ้อนในการคำนวณ
• ประสิทธิภาพของคอมพิวเตอร์ — ตัวชี้วัดฮาร์ดแวร์คอมพิวเตอร์
• อัลกอริทึมเชิงประจักษ์ — การนำวิธีการเชิงประจักษ์มาใช้ในการศึกษาพฤติกรรมของอัลกอริทึม
• โครงร่างของอัลกอริธึม
• การเพิ่มประสิทธิภาพโปรแกรม
• การวิเคราะห์ประสิทธิภาพ — วิธีการวัดประสิทธิภาพที่แท้จริงของอัลกอริทึมในระหว่างการทำงาน