ในวิทยาการคอมพิวเตอร์เชิงทฤษฎีการวิเคราะห์แบบเรียบเป็นวิธีการวัดความซับซ้อนของอัลกอริทึมนับตั้งแต่มีการนำเสนอในปี 2544 การวิเคราะห์แบบเรียบได้ถูกนำมาใช้เป็นพื้นฐานสำหรับการวิจัยจำนวนมาก สำหรับปัญหาต่างๆ ตั้งแต่ การ ^{เขียน}โปรแกรมทางคณิตศาสตร์การวิเคราะห์เชิงตัวเลขการเรียนรู้ของเครื่องและการขุดข้อมูล [ ^{1 ]}การวิเคราะห์แบบเรียบสามารถให้การวิเคราะห์ประสิทธิภาพในทางปฏิบัติ (เช่น เวลาในการทำงาน อัตราความสำเร็จ คุณภาพการประมาณค่า) ของอัลกอริทึมที่สมจริงยิ่งขึ้น เมื่อเทียบกับการวิเคราะห์ที่ใช้สถานการณ์กรณีเลวร้ายที่สุดหรือกรณีเฉลี่ย

การวิเคราะห์แบบปรับเรียบ (Smoothed complexity) เป็นการผสมผสานระหว่างการวิเคราะห์กรณีเลวร้ายที่สุด (worst-case analysis) และการวิเคราะห์กรณีเฉลี่ย (average-case analysis) ซึ่งได้ประโยชน์จากทั้งสองวิธี โดยจะวัดประสิทธิภาพที่คาดหวังของอัลกอริทึมภายใต้การรบกวนแบบสุ่มเล็กน้อยของข้อมูลป้อนเข้ากรณีเลวร้ายที่สุด หากค่าความซับซ้อนแบบปรับเรียบของอัลกอริทึมต่ำ ก็ไม่น่าเป็นไปได้ที่อัลกอริทึมจะใช้เวลานานในการแก้ปัญหาในทางปฏิบัติที่มีข้อมูลซึ่งอาจมีสัญญาณรบกวนและความไม่แม่นยำเล็กน้อย ผลลัพธ์ความซับซ้อนแบบปรับเรียบเป็นผลลัพธ์เชิงความน่าจะเป็นที่แข็งแกร่ง โดยคร่าวๆ แล้วระบุว่า ในพื้นที่ใกล้เคียงขนาดใหญ่พอสมควรของพื้นที่ข้อมูลป้อนเข้า ข้อมูลป้อนเข้าส่วนใหญ่สามารถแก้ไขได้ง่าย ดังนั้น ค่าความซับซ้อนแบบปรับเรียบที่ต่ำหมายความว่า ความยากของข้อมูลป้อนเข้าเป็นคุณสมบัติที่ "เปราะบาง"

แม้ว่าความซับซ้อนในกรณีที่เลวร้ายที่สุดจะประสบความสำเร็จอย่างกว้างขวางในการอธิบายประสิทธิภาพในทางปฏิบัติของอัลกอริทึมหลายตัว แต่รูปแบบการวิเคราะห์นี้ให้ผลลัพธ์ที่ทำให้เข้าใจผิดสำหรับปัญหาจำนวนหนึ่ง ความซับซ้อนในกรณีที่เลวร้ายที่สุดวัดเวลาที่ใช้ในการแก้ปัญหาอินพุตใดๆ แม้ว่าอินพุตที่ยากต่อการแก้ปัญหาอาจไม่เคยเกิดขึ้นในทางปฏิบัติ ในกรณีเช่นนี้ เวลาการทำงานในกรณีที่เลวร้ายที่สุดอาจแย่กว่าเวลาการทำงานที่สังเกตได้ในทางปฏิบัติมาก ตัวอย่างเช่น ความซับซ้อนในกรณีที่เลวร้ายที่สุดของการแก้ปัญหาโปรแกรมเชิงเส้นโดยใช้ อัลกอริทึม ซิมเพล็กซ์เป็นแบบเลขชี้กำลัง^{[ 2 ]}แม้ว่าจำนวนขั้นตอนที่สังเกตได้ในทางปฏิบัติจะเป็นแบบเชิงเส้นโดยประมาณ^{[ 3 ] [ 4 ]}ในความเป็นจริงแล้ว อัลกอริทึมซิมเพล็กซ์เร็วกว่าวิธีวงรีในทางปฏิบัติมาก แม้ว่าวิธีหลังจะมีความซับซ้อนในกรณีที่เลวร้ายที่สุดแบบ พหุนาม ก็ตาม

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

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

ACMและสมาคมวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีแห่งยุโรปได้มอบรางวัล Gödel ประจำปี 2008 ให้แก่Daniel SpielmanและShanghua Tengสำหรับการพัฒนาการวิเคราะห์แบบเรียบ (Smoothed Analysis) ชื่อ Smoothed Analysis นั้นตั้งขึ้นโดยAlan Edelman [ ^{1 ] ใน}ปี 2010 Spielman ได้รับรางวัล Nevanlinnaสำหรับการพัฒนาการวิเคราะห์แบบเรียบ บทความ JACM ของ Spielman และ Teng เรื่อง "Smoothed analysis of algorithms: Why the simplex algorithm usually takes polynomial time" ยังเป็นหนึ่งในสามผู้ชนะรางวัล Fulkerson ประจำปี 2009 ซึ่งได้รับการสนับสนุนร่วมกันโดยสมาคมการเขียนโปรแกรมทางคณิตศาสตร์ (MPS) และสมาคมคณิตศาสตร์แห่งอเมริกา (AMS)

อัลกอริทึมซิมเพล็กซ์เป็นอัลกอริทึมที่มีประสิทธิภาพมากในทางปฏิบัติ และเป็นหนึ่งในอัลกอริทึมที่โดดเด่นสำหรับการเขียนโปรแกรมเชิงเส้นในทางปฏิบัติ สำหรับปัญหาในทางปฏิบัติ จำนวนขั้นตอนที่อัลกอริทึมดำเนินการจะเป็นเชิงเส้นตามจำนวนตัวแปรและข้อจำกัด^{[ 3 ] [ 4 ]}อย่างไรก็ตาม ในกรณีที่เลวร้ายที่สุดในเชิงทฤษฎี จะใช้ขั้นตอนจำนวนมากแบบเลขชี้กำลังสำหรับกฎการหมุนที่วิเคราะห์ได้สำเร็จส่วนใหญ่ นี่เป็นหนึ่งในแรงจูงใจหลักในการพัฒนาการวิเคราะห์แบบเรียบ^{[ 5 ]}

สำหรับแบบจำลองการรบกวน เราสมมติว่าข้อมูลอินพุตถูกรบกวนด้วยสัญญาณรบกวนจากการกระจายแบบเกาส์เซียนเพื่อวัตถุประสงค์ในการทำให้เป็นมาตรฐาน เราสมมติว่าข้อมูลที่ไม่ถูกรบกวนเป็นไปตามเงื่อนไขสำหรับทุกแถวของเมทริกซ์ สัญญาณรบกวนมีค่าอิสระที่สุ่มมาจากการกระจายแบบเกาส์เซียนที่มีค่าเฉลี่ยและส่วนเบี่ยงเบนมาตรฐานเรากำหนดให้ข้อมูลอินพุตที่ปรับให้เรียบแล้วประกอบด้วยโปรแกรมเชิงเส้น ${\displaystyle {\bar {\mathbf {A} }}\in \mathbb {R} ^{n\times d},{\bar {\mathbf {b} }}\in \mathbb {R} ^{n},\mathbf {c} \in \mathbb {R} ^{d}}$${\displaystyle \|({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})\|_{2}\leq 1}$${\displaystyle ({\bar {\mathbf {a} }}_{i},{\bar {b}}_{i})}$${\displaystyle ({\bar {\mathbf {A} }},{\bar {\mathbf {b} }})}$${\displaystyle ({\hat {\mathbf {A} }},{\hat {\mathbf {b} }})}$${\displaystyle 0}$${\displaystyle \sigma }$${\displaystyle \mathbf {A} ={\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},\mathbf {b} ={\bar {\mathbf {b} }}+{\hat {\mathbf {b} }}}$

เพิ่มสูงสุด

${\displaystyle \mathbf {c^{T}} \cdot \mathbf {x} }$

ขึ้นอยู่กับ

${\displaystyle \mathbf {A} \mathbf {x} \leq \mathbf {b} }$.

หากเวลาการทำงานของอัลกอริธึมของเราบนข้อมูลกำหนดโดยความซับซ้อนที่ราบเรียบของวิธีการซิมเพล็กซ์คือ^{[ 6 ]}${\displaystyle \mathbf {A} ,\mathbf {b} ,\mathbf {c} }$${\displaystyle T(\mathbf {A} ,\mathbf {b} ,\mathbf {c} )}$

${\displaystyle C_{s}(n,d,\sigma ):=\max _{{\bar {\mathbf {A} }},{\bar {\mathbf {b} }},\mathbf {c} }~\mathbb {E} _{{\hat {\mathbf {A} }},{\hat {\mathbf {b} }}}[T({\bar {\mathbf {A} }}+{\hat {\mathbf {A} }},{\bar {\mathbf {b} }}+{\hat {\mathbf {b} }},\mathbf {c} )]={\rm {poly}}(d,\log n,\sigma ^{-1}).}$

ขอบเขตนี้ใช้ได้กับกฎการหมุนเฉพาะที่เรียกว่ากฎจุดยอดเงา กฎจุดยอดเงาช้ากว่ากฎการหมุนที่ใช้กันทั่วไป เช่น กฎของ Dantzig หรือกฎขอบที่ชันที่สุด^{[ 7 ]}แต่มีคุณสมบัติที่ทำให้เหมาะอย่างยิ่งสำหรับการวิเคราะห์ความน่าจะเป็น^{[ 8 ]}

อัลกอริทึม การค้นหาในพื้นที่จำนวนหนึ่งมีเวลาการทำงานในกรณีที่เลวร้ายที่สุดที่ไม่ดี แต่ทำงานได้ดีในทางปฏิบัติ^{[ 9 ]}

ตัวอย่างหนึ่งคือฮิวริสติก2-opt สำหรับปัญหาพนักงานขายเดินทางอาจต้องใช้การวนซ้ำจำนวนมากแบบเลขชี้กำลังจนกว่าจะพบวิธีแก้ปัญหาที่เหมาะสมที่สุดในระดับท้องถิ่น แม้ว่าในทางปฏิบัติเวลาในการทำงานจะน้อยกว่ากำลังสองของจำนวนจุดยอดก็ตาม^{[ 10 ]}อัตราส่วนการประมาณค่าซึ่งเป็นอัตราส่วนระหว่างความยาวของเอาต์พุตของอัลกอริทึมและความยาวของวิธีแก้ปัญหาที่เหมาะสมที่สุด มักจะดีในทางปฏิบัติ แต่ก็อาจแย่ได้ในกรณีที่เลวร้ายที่สุดในทางทฤษฎี

ปัญหาประเภทหนึ่งสามารถกำหนดได้ด้วยจุดในกล่องโดยที่ระยะห่างระหว่างคู่ของจุดเหล่านั้นมาจากค่ามาตรฐานแม้แต่ในสองมิติ ฮิวริสติก 2-opt อาจใช้การวนซ้ำจำนวนมากแบบเลขชี้กำลังจนกว่าจะพบค่าเหมาะสมที่สุดเฉพาะที่ในการตั้งค่านี้ เราสามารถวิเคราะห์แบบจำลองการรบกวนได้ โดยที่จุดยอดจะถูกสุ่มอย่างอิสระตามการแจกแจงความน่าจะเป็นด้วยฟังก์ชันความหนาแน่นของความน่าจะเป็นสำหรับจุดต่างๆ จะกระจายอย่างสม่ำเสมอ เมื่อมีขนาดใหญ่ ฝ่ายตรงข้ามจะมีศักยภาพมากขึ้นในการเพิ่มความน่าจะเป็นของปัญหาที่ยาก ในแบบจำลองการรบกวนนี้ จำนวนการวนซ้ำที่คาดหวังของฮิวริสติก 2-opt รวมถึงอัตราส่วนการประมาณค่าของผลลัพธ์ที่ได้ จะถูกจำกัดด้วยฟังก์ชันพหุนามของและ^{[ 10 ]}${\displaystyle n}$${\displaystyle [0,1]^{d}}$${\displaystyle v_{1},\dots ,v_{n}}$${\displaystyle f_{1},\dots ,f_{n}:[0,1]^{d}\rightarrow [0,\theta ]}$${\displaystyle \theta =1}$${\displaystyle \theta >1}$${\displaystyle n}$${\displaystyle \theta }$

อัลกอริทึมการค้นหา แบบโลคอ ลอีกตัวหนึ่งที่การวิเคราะห์แบบเรียบประสบความสำเร็จคือวิธี k-meansเมื่อกำหนดจุดใน การหาการแบ่งกลุ่มที่ดีด้วยระยะห่างระหว่างจุดในกลุ่มเดียวกันที่น้อยนั้นเป็นปัญหา NP-hard อัลกอริทึมของ Lloydถูกใช้กันอย่างแพร่หลายและรวดเร็วมากในทางปฏิบัติ แม้ว่าในกรณีที่เลวร้ายที่สุดอาจต้องใช้การวนซ้ำหลายครั้งเพื่อหาคำตอบที่เหมาะสมที่สุดในระดับท้องถิ่น อย่างไรก็ตาม สมมติว่าจุดต่างๆ มีการกระจายแบบเกาส์เซียน^ที่ เป็นอิสระ โดยแต่ละจุดมีค่าเฉลี่ยในและค่าเบี่ยงเบนมาตรฐานจำนวนการวนซ้ำโดยเฉลี่ยของอัลกอริทึมจะถูกจำกัดด้วยพหุนามในและ^[ 11 ^]${\displaystyle n}$${\displaystyle [0,1]^{d}}$${\displaystyle e^{\Omega (n)}}$${\displaystyle [0,1]^{d}}$${\displaystyle \sigma }$${\displaystyle n}$${\displaystyle d}$${\displaystyle \sigma }$

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

• Chen, Deng และ Teng ^{[ 12 ]}พิสูจน์ว่าไม่มีอัลกอริทึมใดที่เป็นพหุนามใน n และ 1/ε ที่สามารถคำนวณสมดุลแนชโดยประมาณ ε ในเกมสองผู้เล่นที่มี การกระทำ nครั้งต่อผู้เล่น เว้นแต่PPAD ≤ P โดยเฉพาะอย่างยิ่ง หมายความว่าอาจไม่มีFPTASสำหรับ NE พวกเขายังพิสูจน์ว่าไม่มีอัลกอริทึมใดสำหรับการคำนวณ NE ในเกมสองผู้เล่นที่มีความซับซ้อนแบบเรียบที่เป็นพหุนามในnและ 1/ sโดยที่sคือขนาดการรบกวนอินพุต เว้นแต่ PPAD ≤ RPโดยเฉพาะอย่างยิ่ง ความซับซ้อนแบบเรียบของ อัลกอริทึม Lemke-Howsonอาจไม่ใช่พหุนาม
• Boodaghians, Brakensiek, Hopkins และ Rubinstein ^{[ 13 ]}พิสูจน์ว่าการคำนวณ NE ในเกม 2 ผู้เล่นนั้นยากแบบ PPAD (ภายใต้การลดแบบสุ่ม) แม้ว่าจะปรับให้เรียบด้วยสัญญาณรบกวนที่มีขนาดคงที่ก็ตาม

• ความซับซ้อนในกรณีเฉลี่ย
• เวลาพсевโดพหุนาม
• ความซับซ้อนในกรณีที่เลวร้ายที่สุด