Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
ในการวิเคราะห์ประสิทธิภาพของของอัลกอริทึม กรณีดีที่สุด (best case) กรณีแย่ที่สุด (worst case) และ กรณีเฉลี่ย (average case) คือ อัตราการใช้ทรัพยากรของอัลกอริทึมอย่างน้อยที่สุด มากที่สุด และ โดยเฉลี่ย ตามลำดับ โดยมักใช้สัญกรณ์โอใหญ่ (big O notation) ในการแสดงอัตราการใช้ทรัพยากรของอัลกอริทึมในแต่ละกรณี
ทรัพยากรที่อัลกอริทึมใช้ สามารถแบ่งได้เป็น 2 ด้าน คือ ด้านเวลา ใช้เวลาในการรัน (running time) หรือเรียกว่า ความซับซ้อนด้านเวลา (time complexity) เป็นหลัก ด้านที่สองคือ การใช้พื้นที่ความจำ (memory space) ของคอมพิวเตอร์ในการรันอัลกอริทึม หรือเรียกว่า ความซับซ้อนด้านพื้นที่ (space complexity)
กรณีที่ดีที่สุด คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่รันได้รวดเร็วที่สุด ใช้ขั้นตอนในการรันต่ำที่สุดสำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟอง (bubble sort algorithm) กรณีที่ดีที่สุด คือ กรณีที่อินพุตที่เป็นตัวเลข เรียงจากน้อยไปมากเรียบร้อยแล้ว ทำให้เวลาอัลกอริทึมรันผ่านอินพุตแต่ละตัว จะใช้เวลาแค่ 1 หน่วยต่ออินพุตหนึ่งตัว มีฟังก์ชัน Big-O คือ O(n)
กรณีที่แย่ที่สุด คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่ที่รันได้ช้าที่สุด อัลกอริทึมใช้ขั้นตอนในการรันมากที่สุด สำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟองกรณีที่แย่ที่สุด คือ กรณีที่อินพุตที่เป็นตัวเลข เรียงจากมากไปน้อย ทำให้เวลาอัลกอริทึมรันผ่านอินพุตแต่ละตัวจะใช้เวลานาน (รันจากตัวแรกไปตัวสุดท้าย ใช้เวลา O(n) รวมกับวนลูปข้างใน ใช้เวลา O(n)) กรณีนี้มีฟังก์ชัน Big-O คือ O(n^2)
กรณีเฉลี่ย คือ ฟังก์ชัน Big-O ในกรณีที่อัลกอริทึมได้รับอินพุต ในแบบที่ที่รันแบบเฉลี่ย อัลกอริทึมใช้ขั้นตอนในการรันโดยเฉลี่ย สำหรับการรันอินพุต n ชิ้น ยกตัวอย่างเช่น อัลกอริทึมเรียงแบบฟองกรณีเฉลี่ย ใช้เวลา O(n^2)
ตัวอย่าง
อัลกอริทึมเรียงลำดับ (Sorting algorithms)
| อัลกอริทึม (Algorithm) | โครงสร้างข้อมูล (Data structure) | ความซับซ้อนทางเวลาในกรณีดีที่สุด | ความซับซ้อนทางเวลาในกรณีเฉลี่ย | ความซับซ้อนทางเวลาในกรณีแย่ที่สุด | ความซับซ้อนทางพื้นที่ในกรณีแย่ที่สุด |
|---|---|---|---|---|---|
| ควิกซอร์ต (Quick sort) | Array | O(n log(n)) | O(n log(n)) | O(n2) | O(n) |
| เมิร์จซอร์ต (Merge sort) | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(n) |
| ฮีพซอร์ต (Heap sort) | Array | O(n log(n)) | O(n log(n)) | O(n log(n)) | O(1) |
| (Smooth sort) | Array | O(n) | O(n log(n)) | O(n log(n)) | O(1) |
| บับเบิลซอร์ต (Bubble sort) | Array | O(n) | O(n2) | O(n2) | O(1) |
| อินเซอร์ชั่นซอร์ต (Insertion sort) | Array | O(n) | O(n2) | O(n2) | O(1) |
| ซีเล็กชั่นซอร์ต (Selection sort) | Array | O(n2) | O(n2) | O(n2) | O(1) |
| โบโก้ซอร์ต (Bogo sort) | Array | O(n) | O(n n!) | O(∞) | O(1) |
- ควิกซอร์ต (Quicksort) ใช้ในการจัดเรียงลิสต์ที่มีสมาชิกอยู่ n ตัว โดยตั้งสมมติฐานว่าแต่ละตัวแตกต่างกัน (ไม่มีตัวไหนซ้ำกัน) โดยเป็นอัลกอริทึมที่ได้รับความนิยมใช้อย่างสูง อัลกอริทึมนี้มีประสิทธิภาพการเรียงในกรณีเฉลี่ยอยู่ที่ O(n log(n)) ทำให้อัลกอริทึมนี้เป็นอัลกอริทึมที่มีความเร็วสูงมากในการนำไปใช้งานจริง แต่ในกรณีที่แย่ที่สุด ควิกซอร์ตจำมีประสิทธิภาพการเรียงตกลงไปอยู่ที่ O(n2).
อ้างอิง
- Introduction to Algorithms (Cormen, Leiserson, Rivest, and Stein) 2001, Chapter 2 "Getting Started".In Best-case complexity, it gives the lower bound on the running time of the algorithm of any instances of input.
- Lovász László (2009). Algoritmusok Bonyolultsága (ความซับซ้อนของอัลกอริทึม). Eötvös Loránd University. ลิงก์: https://www.uni-miskolc.hu/~matha/Gacs_Lovasz.pdf 2021-12-30 ที่ เวย์แบ็กแมชชีน
- Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. .
wikipedia, แบบไทย, วิกิพีเดีย, วิกิ หนังสือ, หนังสือ, ห้องสมุด, บทความ, อ่าน, ดาวน์โหลด, ฟรี, ดาวน์โหลดฟรี, mp3, วิดีโอ, mp4, 3gp, jpg, jpeg, gif, png, รูปภาพ, เพลง, เพลง, หนัง, หนังสือ, เกม, เกม, มือถือ, โทรศัพท์, Android, iOS, Apple, โทรศัพท์โมบิล, Samsung, iPhone, Xiomi, Xiaomi, Redmi, Honor, Oppo, Nokia, Sonya, MI, PC, พีซี, web, เว็บ, คอมพิวเตอร์
inkarwiekhraahprasiththiphaphkhxngkhxngxlkxrithum krnidithisud best case krniaeythisud worst case aela krniechliy average case khux xtrakarichthrphyakrkhxngxlkxrithumxyangnxythisud makthisud aela odyechliy tamladb odymkichsykrnoxihy big O notation inkaraesdngxtrakarichthrphyakrkhxngxlkxrithuminaetlakrni thrphyakrthixlkxrithumich samarthaebngidepn 2 dan khux danewla ichewlainkarrn running time hruxeriykwa khwamsbsxndanewla time complexity epnhlk danthisxngkhux karichphunthikhwamca memory space khxngkhxmphiwetxrinkarrnxlkxrithum hruxeriykwa khwamsbsxndanphunthi space complexity krnithidithisud khux fngkchn Big O inkrnithixlkxrithumidrbxinphut inaebbthirnidrwderwthisud ichkhntxninkarrntathisudsahrbkarrnxinphut n chin yktwxyangechn xlkxrithumeriyngaebbfxng bubble sort algorithm krnithidithisud khux krnithixinphutthiepntwelkh eriyngcaknxyipmakeriybrxyaelw thaihewlaxlkxrithumrnphanxinphutaetlatw caichewlaaekh 1 hnwytxxinphuthnungtw mifngkchn Big O khux O n krnithiaeythisud khux fngkchn Big O inkrnithixlkxrithumidrbxinphut inaebbthithirnidchathisud xlkxrithumichkhntxninkarrnmakthisud sahrbkarrnxinphut n chin yktwxyangechn xlkxrithumeriyngaebbfxngkrnithiaeythisud khux krnithixinphutthiepntwelkh eriyngcakmakipnxy thaihewlaxlkxrithumrnphanxinphutaetlatwcaichewlanan rncaktwaerkiptwsudthay ichewla O n rwmkbwnlupkhangin ichewla O n krninimifngkchn Big O khux O n 2 krniechliy khux fngkchn Big O inkrnithixlkxrithumidrbxinphut inaebbthithirnaebbechliy xlkxrithumichkhntxninkarrnodyechliy sahrbkarrnxinphut n chin yktwxyangechn xlkxrithumeriyngaebbfxngkrniechliy ichewla O n 2 twxyangxlkxrithumeriyngladb Sorting algorithms xlkxrithum Algorithm okhrngsrangkhxmul Data structure khwamsbsxnthangewlainkrnidithisud khwamsbsxnthangewlainkrniechliy khwamsbsxnthangewlainkrniaeythisud khwamsbsxnthangphunthiinkrniaeythisudkhwiksxrt Quick sort Array O n log n O n log n O n2 O n emircsxrt Merge sort Array O n log n O n log n O n log n O n hiphsxrt Heap sort Array O n log n O n log n O n log n O 1 Smooth sort Array O n O n log n O n log n O 1 bbebilsxrt Bubble sort Array O n O n2 O n2 O 1 xinesxrchnsxrt Insertion sort Array O n O n2 O n2 O 1 sielkchnsxrt Selection sort Array O n2 O n2 O n2 O 1 oboksxrt Bogo sort Array O n O n n O O 1 krafkhxngfngkchnthiichthwipinkarwiekhraahxlkxrithum aesdngcanwnkardaeninkar N ethiybkbkhnadxinphut n sahrbaetlafngkchnkhwiksxrt Quicksort ichinkarcderiynglistthimismachikxyu n tw odytngsmmtithanwaaetlatwaetktangkn immitwihnsakn odyepnxlkxrithumthiidrbkhwamniymichxyangsung xlkxrithumnimiprasiththiphaphkareriynginkrniechliyxyuthi O n log n thaihxlkxrithumniepnxlkxrithumthimikhwamerwsungmakinkarnaipichngancring aetinkrnithiaeythisud khwiksxrtcamiprasiththiphaphkareriyngtklngipxyuthi O n2 xangxingIntroduction to Algorithms Cormen Leiserson Rivest and Stein 2001 Chapter 2 Getting Started In Best case complexity it gives the lower bound on the running time of the algorithm of any instances of input Lovasz Laszlo 2009 Algoritmusok Bonyolultsaga khwamsbsxnkhxngxlkxrithum Eotvos Lorand University lingk https www uni miskolc hu matha Gacs Lovasz pdf 2021 12 30 thi ewyaebkaemchchin Sipser Michael 2006 Introduction to the Theory of Computation Course Technology Inc ISBN 0 619 21764 2