วิกิพีเดียภาษาไทย
กลับไปหน้าบทความ

อ่าน 36 นาที

สัญกรณ์บิ๊กโอ

การเปลี่ยนเส้นทางที่กล่าวถึงใน hatnotes/เปลี่ยนเส้นทางไปยังส่วนต่างๆ

สัญกรณ์Big Oเป็นสัญกรณ์ทางคณิตศาสตร์ที่อธิบายขนาดโดยประมาณของฟังก์ชันบนโดเมน Big O เป็นสมาชิกของกลุ่มสัญกรณ์ที่คิดค้นโดยนักคณิตศาสตร์ชาวเยอรมันPaul Bachmann และEdmund Landau...

สัญกรณ์บิ๊กโอ

สัญกรณ์Big Oเป็นสัญกรณ์ทางคณิตศาสตร์ที่อธิบายขนาดโดยประมาณของฟังก์ชันบนโดเมน Big O เป็นสมาชิกของกลุ่มสัญกรณ์ที่คิดค้นโดยนักคณิตศาสตร์ชาวเยอรมันPaul Bachmann [ 1 ]และEdmund Landau [ 2 ]และขยายโดยคนอื่นๆ ซึ่งเรียกรวมกันว่าสัญกรณ์ Bachmann–Landauตัวอักษร O ย่อมาจากOrdnungซึ่งหมาย ถึง ลำดับของการประมาณ

ในวิทยาการคอมพิวเตอร์สัญกรณ์ Big O ใช้ในการจำแนกอัลกอริทึมตามขนาดเวลาการทำงานหรือความต้องการพื้นที่[ a ]ที่เพิ่มขึ้นตามอินพุต[ 3 ]ในทฤษฎีจำนวนเชิงวิเคราะห์ สัญ กรณ์ Big O แสดงขอบเขตของการเติบโตของฟังก์ชันทางคณิตศาสตร์เช่น พจน์เศษเหลือในทฤษฎีบทจำนวนเฉพาะ [ 4 ] ใน การวิเคราะห์ทางคณิตศาสตร์รวมถึงแคลคูลัส สัญกรณ์ Big O กำหนดขอบเขตของข้อผิดพลาดเมื่อตัดทอนอนุกรมกำลังและแสดงคุณภาพของการประมาณค่าฟังก์ชันค่าจริงหรือเชิงซ้อนด้วยฟังก์ชันที่ง่ายกว่า

โดยทั่วไป สัญกรณ์บิ๊กโอ (Big O notation) มักใช้เพื่ออธิบายฟังก์ชันตามอัตราการเติบโตเมื่อตัวแปรมีค่ามาก: ฟังก์ชันต่าง ๆ ที่มี อัตราการเติบโตเชิงเส้น กำกับ (asymptotic growth rate) เท่ากัน อาจแสดงด้วยสัญกรณ์โอเดียวกันได้ ตัวอักษรโอถูกใช้เพราะอัตราการเติบโตของฟังก์ชันเรียกอีกอย่างว่าอันดับของฟังก์ชันการอธิบายฟังก์ชันด้วยสัญกรณ์บิ๊กโอจะให้เพียงขอบเขตบนของอัตราการเติบโตของฟังก์ชัน เท่านั้น

นอกจากสัญกรณ์บิ๊กโอแล้ว ยังมีสัญกรณ์ที่เกี่ยวข้องอีกหลายแบบ โดยใช้สัญลักษณ์ต่างๆ กันโอ{\displaystyle o},~{\displaystyle \sim },Ω{\displaystyle \Omega },≪{\displaystyle \ll },≫{\displaystyle \gg },≍{\displaystyle \asymp },ω{\displaystyle \omega }, และΘ{\displaystyle \Theta }เพื่ออธิบายขอบเขตประเภทอื่นๆ ของอัตราการเติบโต[ 5 ] [ 6 ] [ 7 ] [ 8 ]

Bachmann เสนอสัญกรณ์นี้ในปี พ.ศ. 2337 และ Landau ขยายสัญกรณ์นี้ในปี พ.ศ. 2452 สัญกรณ์ก่อนหน้านี้ได้รับการเสนอโดยPaul du Bois-Reymondในปี พ.ศ. 2413 [ 9 ]

คำจำกัดความอย่างเป็นทางการ

อนุญาตเอฟ,{\textstyle f,}ฟังก์ชันที่จะประมาณค่า อาจเป็น ฟังก์ชันค่า จริงหรือ ค่า เชิงซ้อนที่กำหนดบนโดเมนดี,{\textstyle D,}และปล่อยให้จี,{\textstyle g,}ฟังก์ชันเปรียบเทียบ ต้องเป็นฟังก์ชันค่าจริงที่ไม่เป็นลบ ซึ่งกำหนดบนเซตเดียวกันดี.{\textstyle D.}ตัวเลือกทั่วไปสำหรับโดเมน ได้แก่ ช่วงของจำนวนจริง ทั้งแบบมีขอบเขตและไม่มีขอบเขต เซตของจำนวนเต็มบวก เซตของจำนวนเชิงซ้อนและคู่ของจำนวนจริง/จำนวนเชิงซ้อน เมื่อเขียนโดเมนอย่างชัดเจนหรือเข้าใจโดยนัย เราสามารถเขียนได้ว่า

เอฟ(x)=โอ(จี(x)) {\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\ }

ซึ่งอ่านได้ว่า"เอฟ(x){\textstyle f(x)}ใหญ่​โอ{\textstyle O}ของจี(x){\textstyle g(x)}"ถ้ามีจำนวนจริงบวกอยู่จริง"เอ็ม{\textstyle M}โดยที่

|เอฟ(x)|≤เอ็ม จี(x)  เอฟโอร เอลล  x∈ดี.{\displaystyle \left|f(x)\right|\leq M\ g(x)\qquad ~{\mathsf {\ for\ all\ }}~\quad x\in D.}

ถ้าจี(x)>0{\displaystyle g(x)>0}(กล่าวคือgไม่เป็นศูนย์เลย) ตลอดทั้งโดเมนดี,{\displaystyle D,}นิยามที่เทียบเท่ากันคือ อัตราส่วนเอฟ(x)จี(x){\textstyle {\frac {f(x)}{g(x)}}}มีขอบเขตจำกัดกล่าวคือ มีจำนวนจริงบวกอยู่เอ็ม{\displaystyle M}ดังนั้น|เอฟ(x)จี(x)|≤เอ็ม{\textstyle {\Big |}{\frac {f(x)}{g(x)}}{\Big |}\leq M}สำหรับทุกคนx∈ดี.{\displaystyle x\in D.}สิ่งเหล่านี้ครอบคลุมการใช้งานทั้งหมดของขนาดใหญ่โอ{\textstyle O}ในสาขาวิทยาการคอมพิวเตอร์และคณิตศาสตร์ รวมถึงการใช้งานในกรณีที่โดเมนเป็นจำนวนจำกัด จำนวนอนันต์ จำนวนจริง จำนวนเชิงซ้อน ตัวแปรเดียว หรือหลายตัวแปร ในการใช้งานส่วนใหญ่ มักจะเลือกฟังก์ชันจี(x){\displaystyle g(x)}ปรากฏอยู่ภายในข้อโต้แย้งของโอ(⋅){\textstyle O{\bigl (}\cdot {\bigr )}}เพื่อให้เป็นรูปแบบที่ง่ายที่สุดเท่าที่จะเป็นไปได้ โดยตัดค่าคงที่และพจน์ลำดับต่ำกว่าออกไป จำนวนเอ็ม{\textstyle M}เรียกว่าค่าคงที่โดยนัยเพราะโดยปกติไม่ได้ระบุไว้ เมื่อใช้ค่าขนาดใหญ่โอ{\textstyle O}ในแง่ของสัญลักษณ์ สิ่งสำคัญคือต้องมีค่าจำกัดบางอย่างเอ็ม{\displaystyle M}สิ่งที่ปรากฏอยู่ ไม่ใช่ค่าเฉพาะของมัน วิธีนี้ช่วยให้การนำเสนออสมการเชิงวิเคราะห์หลายอย่างง่ายขึ้น

สำหรับฟังก์ชันที่กำหนดบนจำนวนจริงบวกหรือจำนวนเต็มบวก คำจำกัดความที่เข้มงวดกว่าและขัดแย้งกันเล็กน้อยยังคงใช้กันทั่วไป[ 3 ] [ 10 ]โดยเฉพาะในวิทยาศาสตร์คอมพิวเตอร์ เมื่อจำกัดเฉพาะฟังก์ชันที่เป็น บวก ในที่สุดสัญกรณ์

เอฟ(x)=โอ(จี(x)) เอสx→∞{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\mathsf {as}}\quad x\to \infty }

หมายความว่าสำหรับจำนวนจริงบางจำนวนเอ,{\textstyle a,}เอฟ(x)=โอ(จี(x)){\textstyle f(x)=O{\bigl (}g(x){\bigr )}}ในโดเมน[เอ,∞).{\textstyle \left[a,\infty \right).}ในที่นี้ การแสดงออกx→∞{\textstyle x\to \infty }ไม่ได้บ่งชี้ถึงขีดจำกัดแต่หมายถึงแนวคิดที่ว่าอสมการนี้เป็นจริงสำหรับค่าที่มากพอx.{\textstyle x.}การแสดงออกx→∞{\textstyle x\to \infty }มักจะถูกละเว้น[ 3 ]

ในทำนองเดียวกัน สำหรับจำนวนจริงเอ,{\textstyle a,}สัญลักษณ์

เอฟ(x)=โอ(จี(x))  เช่น  x→เอ{\displaystyle f(x)=O{\bigl (}g(x){\bigr )}\qquad ~{\text{ as }}\ x\to a}

หมายความว่าสำหรับค่าคงที่บางค่าซี>0,{\textstyle c>0,}เอฟ(x)=โอ(จี(x)){\textstyle f(x)=O{\bigl (}g(x){\bigr )}}ในช่วงเวลา[เอ−ซี,เอ+ซี];{\displaystyle \left[a-c,a+c\right];}นั่นคือ ในย่านเล็กๆ แห่งหนึ่งเอ.{\displaystyle a.} นอกจากนี้ สัญลักษณ์ดังกล่าว  เอฟ(x)=ชม.(x)+โอ(จี(x)) {\displaystyle \ f(x)=h(x)+O{\bigl (}g(x){\bigr )}\ } วิธีเอฟ(x)−ชม.(x)=โอ(จี(x)).{\textstyle f(x)-h(x)=O{\bigl (}g(x){\bigr )}.}สามารถใช้สำนวนที่ซับซ้อนกว่านี้ ได้เช่นกัน

ถึงแม้จะมีเครื่องหมายเท่ากับ ( = ) ปรากฏอยู่ตามที่เขียนไว้ แต่การแสดงออกนั้นเอฟ(x)=โอ(จี(x)){\textstyle f(x)=O{\bigl (}g(x){\bigr )}}ไม่ได้หมายถึงความเท่าเทียมกันแต่หมายถึงความไม่เท่าเทียมกันที่เกี่ยวข้องเอฟ{\textstyle f}และจี.{\textstyle g.}

ในช่วงทศวรรษ 1930 [ 6 ]นักทฤษฎีจำนวนชาวรัสเซียIM Vinogradovได้นำสัญลักษณ์นี้มาใช้≪,{\displaystyle \ll ,}ซึ่งถูกนำมาใช้มากขึ้นในทฤษฎีจำนวน[ 4 ] [ 11 ] [ 12 ]และสาขาอื่นๆ ของคณิตศาสตร์ เป็นทางเลือกแทนโอ{\textstyle O}สัญกรณ์ เรามี

 เอฟ≪จี⟺เอฟ=โอ(จี).{\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}

บ่อยครั้งที่มีการใช้สัญลักษณ์ทั้งสองแบบในงานเขียนเดียวกัน

เวอร์ชั่นเซ็ตของบิ๊กโอ

ในวิทยาการคอมพิวเตอร์[ 3 ]เป็นเรื่องปกติที่จะกำหนดขนาดใหญ่โอ{\textstyle O}รวมถึงการกำหนดชุดฟังก์ชันด้วย โดยใช้ฟังก์ชันที่เป็นบวก (หรือไม่เป็นลบ)จี(x){\displaystyle g(x)}ตามที่ระบุไว้ การตีความหนึ่งโอ(จี(x)){\textstyle O{\bigl (}g(x){\bigr )}}ในฐานะตัวแทนของเซตของฟังก์ชันทั้งหมดเอฟ~{\textstyle {\tilde {f}}}ที่ทำให้พึงพอใจเอฟ~(x)=โอ(จี(x)).{\textstyle {\tilde {f}}(x)=O{\bigl (}g(x){\bigr )}.}จากนั้นเราสามารถเขียนในทำนองเดียวกันได้เอฟ(x)∈โอ(จี(x)),{\textstyle f(x)\in O{\bigl (}g(x){\bigr )},}อ่านว่า "ฟังก์ชัน" เอฟ(x) {\textstyle \ f(x)\ }อยู่ในกลุ่มของฟังก์ชันลำดับทั้งหมดอย่างมากที่สุดจี(x).{\textstyle g(x).}"

ตัวอย่างที่มีโดเมนอนันต์

ในการใช้งานทั่วไปโอ{\displaystyle O}สัญลักษณ์นี้ใช้กับช่วงอนันต์ของจำนวนจริง[เอ,∞){\displaystyle [a,\infty )}และจับภาพพฤติกรรมของฟังก์ชันสำหรับค่าขนาดใหญ่มากx{\displaystyle x}ในบริบทนี้ การมีส่วนร่วมของคำศัพท์ที่เติบโต "เร็วที่สุด" จะทำให้คำศัพท์อื่นๆ กลายเป็นสิ่งที่ไม่สำคัญในที่สุด ดังนั้นจึงสามารถใช้กฎการลดรูปต่อไปนี้ได้:

  • ถ้าเอฟ(x){\displaystyle f(x)}เป็นผลรวมของหลายพจน์ หากมีพจน์ใดที่มีอัตราการเติบโตสูงสุด ก็สามารถเก็บไว้และตัดพจน์อื่นๆ ทิ้งได้
  • ถ้าเอฟ(x){\displaystyle f(x)}เป็นผลคูณของปัจจัยหลายอย่าง โดยมีค่าคงที่ใดๆ (ปัจจัยในผลคูณที่ไม่ขึ้นอยู่กับ)x{\displaystyle x}) สามารถละเว้นได้

ตัวอย่างเช่น สมมติว่าเอฟ(x)=6x4−2x3+5{\displaystyle f(x)=6x^{4}-2x^{3}+5}และสมมติว่าเราต้องการทำให้ฟังก์ชันนี้ง่ายขึ้น โดยใช้โอ{\displaystyle O}สัญลักษณ์ที่ใช้อธิบายอัตราการเติบโตสำหรับค่าขนาดใหญ่x{\displaystyle x}ฟังก์ชันนี้เป็นผลรวมของสามพจน์:6x4{\displaystyle 6x^{4}},−2x3{\displaystyle -2x^{3}}, และ5{\displaystyle 5}ในบรรดาสามพจน์นี้ พจน์ที่มีอัตราการเติบโตสูงสุดคือพจน์ที่มีเลขชี้กำลังมากที่สุดเมื่อพิจารณาเป็นฟังก์ชันของx{\displaystyle x}กล่าวคือ6x4{\displaystyle 6x^{4}}ทีนี้เราสามารถใช้กฎข้อที่สองได้:6x4{\displaystyle 6x^{4}}เป็นผลผลิตจาก6{\displaystyle 6}และx4{\displaystyle x^{4}}ซึ่งปัจจัยแรกไม่ขึ้นอยู่กับx{\displaystyle x}การละเว้นปัจจัยนี้จะทำให้ได้รูปแบบที่เรียบง่ายขึ้นx4{\displaystyle x^{4}}ดังนั้น เราจึงกล่าวว่าเอฟ(x){\displaystyle f(x)}เป็น "โอใหญ่" ของx4{\displaystyle x^{4}}ในทางคณิตศาสตร์ เราสามารถเขียนได้ว่าเอฟ(x)=โอ(x4){\displaystyle f(x)=O(x^{4})}สำหรับทุกคนx≥1{\displaystyle x\geq 1}เราสามารถยืนยันการคำนวณนี้ได้โดยใช้คำจำกัดความอย่างเป็นทางการ: ให้เอฟ(x)=6x4−2x3+5{\displaystyle f(x)=6x^{4}-2x^{3}+5}และจี(x)=x4{\displaystyle g(x)=x^{4}}เมื่อนำ นิยามอย่างเป็นทางการ จากข้างต้น มาใช้ข้อความที่ว่าเอฟ(x)=โอ(x4){\displaystyle f(x)=O(x^{4})}เทียบเท่ากับการขยายตัวของมัน |เอฟ(x)|≤เอ็มx4{\displaystyle |f(x)|\leq Mx^{4}} สำหรับการเลือกจำนวนจริงบวกที่เหมาะสมบางจำนวนเอ็ม{\displaystyle M}และสำหรับทุกคนx≥1{\displaystyle x\geq 1}เพื่อพิสูจน์สิ่งนี้ ให้กำหนดเอ็ม=13{\displaystyle M=13}จากนั้น สำหรับทุกคนx≥1{\displaystyle x\geq 1}: |6x4−2x3+5|≤6x4+|−2x3|+5≤6x4+2x4+5x4=13x4{\displaystyle {\begin{aligned}|6x^{4}-2x^{3}+5|&\leq 6x^{4}+|-2x^{3}|+5\\&\leq 6x^{4}+2x^{4}+5x^{4}\\&=13x^{4}\end{aligned}}} ดังนั้น |6x4−2x3+5|≤13x4.{\displaystyle |6x^{4}-2x^{3}+5|\leq 13x^{4}.} ถึงแม้ว่าจะเป็นความจริงเช่นกัน ด้วยเหตุผลเดียวกันที่ว่า เอฟ(x)=โอ(x10){\displaystyle f(x)=O(x^{10})}นี่เป็นการประมาณค่าฟังก์ชันที่ไม่แม่นยำนักเอฟ{\displaystyle f}ในทางกลับกัน คำกล่าวนี้เอฟ(x)=โอ(x3){\displaystyle f(x)=O(x^{3})}เป็นเท็จ เพราะเงื่อนไข6x4{\displaystyle 6x^{4}}สาเหตุ เอฟ(x)/x3{\displaystyle f(x)/x^{3}}ไร้ขอบเขต

เมื่อฟังก์ชันที(n){\displaystyle T(n)}อธิบายจำนวนขั้นตอนที่จำเป็นในอัลกอริทึมที่มีข้อมูลป้อนเข้าn{\displaystyle n}การแสดงออกเช่นนั้น ที(n)=โอ(n2){\displaystyle T(n)=O(n^{2})} โดยที่โดเมนโดยนัยคือเซตของจำนวนเต็มบวก อาจตีความได้ว่าอัลกอริทึมนี้มีลำดับอย่างมากที่สุดเท่ากับn2{\displaystyle n^{2}}ความซับซ้อนเชิงเวลา

ตัวอย่างที่มีโดเมนจำกัด

นอกจากนี้ ยังสามารถใช้ Big O เพื่ออธิบายพจน์ความคลาดเคลื่อนในการประมาณค่าฟังก์ชันทางคณิตศาสตร์บนช่วงจำกัดได้อีกด้วย พจน์ที่มีนัยสำคัญที่สุดจะถูกเขียนออกมาอย่างชัดเจน จากนั้นพจน์ที่มีนัยสำคัญน้อยที่สุดจะถูกสรุปไว้ในพจน์ Big O เดียว ตัวอย่างเช่น พิจารณาอนุกรมเลขชี้กำลังและนิพจน์สองแบบของมันที่ใช้ได้เมื่อx{\displaystyle x}มีขนาดเล็ก: อีx=1+x+x2 2!+x3 3!+x4 4!+⋯ สำหรับค่าจำกัดทั้งหมด x=1+x+x2 2+โอ(|x|3) สำหรับทุกคน |x|≤1=1+x+โอ(x2) สำหรับทุกคน |x|≤1.{\displaystyle {\begin{aligned}e^{x}&=1+x+{\frac {\;x^{2}\ }{2!}}+{\frac {\;x^{3}\ }{3!}}+{\frac {\;x^{4}\ }{4!}}+\dotsb &&{\text{ for all finite }}x\\[4pt]&=1+x+{\frac {\;x^{2}\ }{2}}+O(|x|^{3})&&{\text{ for all }}|x|\leq 1\\[4pt]&=1+x+O(x^{2})&&{\text{ for all }}|x|\leq 1.\end{aligned}}} การแสดงออกตรงกลาง(บรรทัดที่มี"โอ(|x3|){\displaystyle O(|x^{3}|)}" )หมายถึงค่าสัมบูรณ์ของข้อผิดพลาด  อีx−(1+x+x2 2) {\displaystyle \ e^{x}-(1+x+{\frac {\;x^{2}\ }{2}})\ }อย่างมากก็คงที่ในช่วงเวลาบางช่วง |x3| {\displaystyle ~|x^{3}|\ }เมื่อไร x {\displaystyle \ x~}มีขนาดเล็ก นี่เป็นตัวอย่างหนึ่งของการใช้ทฤษฎีบทของเทย์เลอร์

พฤติกรรมของฟังก์ชันที่กำหนดอาจแตกต่างกันอย่างมากในโดเมนจำกัดเมื่อเทียบกับโดเมนอนันต์ ตัวอย่างเช่น (x+1)8=x8+โอ(x7) สำหรับ x≥1{\displaystyle (x+1)^{8}=x^{8}+O(x^{7})\quad {\text{ for }}x\geq 1} ในขณะที่ (x+1)8=1+8x+โอ(x2) สำหรับ |x|≤1.{\displaystyle (x+1)^{8}=1+8x+O(x^{2})\quad {\text{ for }}|x|\leq 1.}

ตัวอย่างหลายตัวแปร

xบาป⁡y=โอ(x) สำหรับ x≥1,y จำนวนจริงใดๆ{\displaystyle x\sin y=O(x)\quad {\text{ for }}x\geq 1,y{\text{ any real number}}}

3เอ2+7เอข+2ข2+เอ+3ข+14≪เอ2+ข2≪เอ2 สำหรับทุกคน เอ≥ข≥1{\displaystyle 3a^{2}+7ab+2b^{2}+a+3b+14\ll a^{2}+b^{2}\ll a^{2}\quad {\text{ for all }}a\geq b\geq 1}

xyx2+y2=โอ(1) สำหรับความจริงทั้งหมด x,y ที่ไม่ใช่ทั้งสองอย่าง 0{\displaystyle {\frac {xy}{x^{2}+y^{2}}}=O(1)\quad {\text{ for all real }}x,y{\text{ that are not both }}0}

xฉันที=โอ(1) สำหรับ x≠0,ที∈อาร์.{\displaystyle x^{it}=O(1)\quad {\text{ for }}x\neq 0,t\in \mathbb {R} .}

ในที่นี้เรามี ฟังก์ชัน ตัวแปรเชิงซ้อนของตัวแปรสองตัว โดยทั่วไปแล้ว ฟังก์ชันที่มีขอบเขตใดๆ ก็ตามจะเป็นโอ(1){\displaystyle O(1)}.

(x+y)10=โอ(x10) สำหรับ x≥1,−2≤y≤2.{\displaystyle (x+y)^{10}=O(x^{10})\quad {\text{ for }}x\geq 1,-2\leq y\leq 2.}

ตัวอย่างสุดท้ายแสดงให้เห็นถึงการผสมผสานระหว่างโดเมนจำกัดและโดเมนอนันต์บนตัวแปรต่างๆ

ในตัวอย่างทั้งหมดนี้ ขอบเขตจะเป็นค่าเดียวกันในตัวแปรทั้งสอง บางครั้งในนิพจน์หลายตัวแปร ตัวแปรหนึ่งอาจมีความสำคัญมากกว่าตัวแปรอื่น และเราอาจแสดงค่าคงที่โดยนัยได้เอ็ม{\displaystyle M}ขึ้นอยู่กับตัวแปรอย่างน้อยหนึ่งตัวโดยใช้ดัชนีของสัญลักษณ์ O ตัวใหญ่หรือ≪{\displaystyle \ll }สัญลักษณ์ ตัวอย่างเช่น พิจารณาการแสดงออก

(1+x)ข=1+โอข(x) สำหรับ 0≤x≤1,ข จำนวนจริงใดๆ{\displaystyle (1+x)^{b}=1+O_{b}(x)\quad {\text{ for }}0\leq x\leq 1,b{\text{ any real number.}}}

หมายความว่าสำหรับจำนวนจริงแต่ละจำนวนข{\displaystyle b}มีค่าคงที่เอ็มข{\displaystyle M_{b}}ซึ่งขึ้นอยู่กับข{\displaystyle b}เพื่อให้สำหรับทุกคน0≤x≤1{\displaystyle 0\leq x\leq 1}, |(1+x)ข−1|≤เอ็มข⋅x.{\displaystyle |(1+x)^{b}-1|\leq M_{b}\cdot x.} ข้อความนี้เป็นผลมาจากทฤษฎีบททวินามทั่วไป

อีกตัวอย่างหนึ่งที่พบได้ทั่วไปในทฤษฎีอนุกรมเทย์เลอร์คือ อีx=1+x+โอร(x2) สำหรับทุกคน |x|≤ร,ร เป็นจำนวนจริงใดๆ ก็ได้{\displaystyle e^{x}=1+x+O_{r}(x^{2})\quad {\text{ for all }}|x|\leq r,r{\text{ being any real number.}}} ในที่นี้ ค่าคงที่โดยนัยจะขึ้นอยู่กับขนาดของโดเมน

หลักการใช้ตัวห้อยใช้กับสัญลักษณ์อื่นๆ ทั้งหมดในหน้านี้

คุณสมบัติ

ผลิตภัณฑ์

เอฟ1=โอ(จี1) และ เอฟ2=โอ(จี2)⇒เอฟ1เอฟ2=โอ(จี1จี2){\displaystyle f_{1}=O(g_{1}){\text{ and }}f_{2}=O(g_{2})\Rightarrow f_{1}f_{2}=O(g_{1}g_{2})}
เอฟ⋅โอ(จี)=โอ(|เอฟ|จี){\displaystyle f\cdot O(g)=O(|f|g)}

ผลรวม

ถ้าเอฟ1=โอ(จี1){\displaystyle f_{1}=O(g_{1})}และเอฟ2=โอ(จี2){\displaystyle f_{2}=O(g_{2})}แล้วเอฟ1+เอฟ2=โอ(สูงสุด(จี1,จี2)){\displaystyle f_{1}+f_{2}=O(\max(g_{1},g_{2}))}ดังนั้น ถ้าเอฟ1=โอ(จี){\displaystyle f_{1}=O(g)}และเอฟ2=โอ(จี){\displaystyle f_{2}=O(g)}แล้วเอฟ1+เอฟ2=โอ(จี){\displaystyle f_{1}+f_{2}=O(g)}.

การคูณด้วยค่าคงที่

ให้kเป็นค่าคงที่ที่ไม่ใช่ศูนย์ แล้วโอ(|เค|⋅จี)=โอ(จี){\displaystyle O(|k|\cdot g)=O(g)}กล่าวอีกนัยหนึ่งคือ ถ้าเอฟ=โอ(จี){\displaystyle f=O(g)}, แล้วเค⋅เอฟ=โอ(จี).{\displaystyle k\cdot f=O(g).}

คุณสมบัติการถ่ายทอด

ถ้าเอฟ=โอ(จี){\displaystyle f=O(g)}และจี=โอ(ชม.){\displaystyle g=O(h)}แล้ว เอฟ=โอ(ชม.){\displaystyle f=O(h)}.

ถ้าฟังก์ชันเอฟ{\displaystyle f}ของจำนวนเต็มบวก n{\displaystyle n}สามารถเขียนได้ในรูปผลรวมจำกัดของฟังก์ชันอื่นๆ จากนั้นฟังก์ชันที่เติบโตเร็วที่สุดจะเป็นตัวกำหนดลำดับของเอฟ(n){\displaystyle f(n)}. ตัวอย่างเช่น,

เอฟ(n)=9บันทึก⁡n+5(บันทึก⁡n)4+3n2+2n3=โอ(n3)สำหรับ n≥1.{\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}

กฎทั่วไปบางประการเกี่ยวกับการเติบโตไปสู่อนันต์ ; คุณสมบัติข้อที่ 2 และ 3 ด้านล่างสามารถพิสูจน์ได้อย่างเคร่งครัดโดยใช้กฎของโลปิตาล :

มหาอำนาจครอบงำมหาอำนาจเล็ก

สำหรับข≥เอ{\displaystyle b\geq a}, แล้ว nเอ=โอ(nข){\displaystyle n^{a}=O(n^{b})} เช่นn→∞{\displaystyle n\to \infty }.

เลขยกกำลังมีอิทธิพลเหนือลอการิทึม

สำหรับผลบวกใดๆเอ,ข,{\displaystyle a,b,}(บันทึก⁡n)เอ=โอเอ,ข(nข),{\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),} ไม่ว่าจะใหญ่แค่ไหนก็ตามเอ{\displaystyle a}คืออะไร และเล็กแค่ไหน ข{\displaystyle b}คือ ในที่นี้ ค่าคงที่โดยนัยขึ้นอยู่กับทั้งสองอย่างเอ{\displaystyle a}และข{\displaystyle b}.

เลขยกกำลังมีอิทธิพลเหนือกว่าเลขยกกำลัง

สำหรับผลบวกใดๆเอ,ข,{\displaystyle a,b,}nเอ=โอเอ,ข(อีขn),{\displaystyle n^{a}=O_{a,b}(e^{bn}),} ไม่ว่าจะใหญ่แค่ไหนก็ตามเอ{\displaystyle a}คืออะไร และเล็กแค่ไหน ข{\displaystyle b}เป็น.

ฟังก์ชันที่เติบโตเร็วกว่าnซี{\displaystyle n^{c}}สำหรับใดๆซี{\displaystyle c}เรียกว่าซูเปอร์โพลินอมิอัลซึ่งเติบโตช้ากว่าฟังก์ชันเลขชี้กำลังใดๆ ที่มีรูปแบบดังกล่าวซีn{\displaystyle c^{n}}กับซี>1{\displaystyle c>1}เรียกว่าแบบซับเอ็กซ์โพเนนเชียลอัลกอริทึมบางอย่างอาจใช้เวลาในการทำงานที่ทั้งเป็นแบบซูเปอร์พหุนามและซับเอ็กซ์โพเนนเชียล ตัวอย่างเช่น อัลกอริทึมที่เร็วที่สุดเท่าที่รู้จักสำหรับการแยกตัวประกอบจำนวนเต็มและฟังก์ชันnบันทึก⁡n{\displaystyle n^{\log n}}.

เราอาจเพิกเฉยต่ออำนาจใดๆ ก็ได้n{\displaystyle n}ภายในลอการิทึม สำหรับค่าบวกใดๆซี{\displaystyle c}สัญลักษณ์โอ(บันทึก⁡n){\displaystyle O(\log n)}หมายความว่าเหมือนกันทุกประการกับโอ(บันทึก⁡(nซี)){\displaystyle O(\log(n^{c}))}, เนื่องจากบันทึก⁡(nซี)=ซีบันทึก⁡n{\displaystyle \log(n^{c})=c\log n}ในทำนองเดียวกัน ลอการิทึมที่มีฐานคงที่ต่างกันจะเทียบเท่ากันเมื่อพิจารณาจากสัญกรณ์ Big O ในทางกลับกัน เลขยกกำลังที่มีฐานต่างกันจะไม่เรียงลำดับเดียวกัน ตัวอย่างเช่น2n{\displaystyle 2^{n}}และ3n{\displaystyle 3^{n}}ไม่ใช่ลำดับเดียวกัน

การแสดงออกที่ซับซ้อนยิ่งขึ้น

ในการใช้งานที่ซับซ้อนกว่านี้โอ(⋅){\displaystyle O(\cdot )}สามารถปรากฏในตำแหน่งต่างๆ ในสมการได้ แม้กระทั่งหลายครั้งในแต่ละด้าน ตัวอย่างเช่น ข้อความต่อไปนี้เป็นจริงสำหรับn{\displaystyle n}จำนวนเต็มบวก: (n+1)2=n2+โอ(n),(n+โอ(n1/2))⋅(n+โอ(บันทึก⁡n))2=n3+โอ(n5/2),nโอ(1)=โอ(อีn).{\displaystyle {\begin{aligned}(n+1)^{2}&=n^{2}+O(n),\\(n+O(n^{1/2}))\cdot (n+O(\log n))^{2}&=n^{3}+O(n^{5/2}),\\n^{O(1)}&=O(e^{n}).\end{aligned}}} ความหมายของข้อความดังกล่าวมีดังนี้: สำหรับฟังก์ชันใดๆ ที่ตรงตามเงื่อนไขแต่ละข้อโอ(⋅){\displaystyle O(\cdot )}ทางด้านซ้าย มีฟังก์ชันบางอย่างที่ ตรงตามข้อกำหนดแต่ละข้อโอ(⋅){\displaystyle O(\cdot )}ทางด้านขวา โดยการแทนฟังก์ชันทั้งหมดเหล่านี้ลงในสมการจะทำให้ทั้งสองข้างเท่ากัน ตัวอย่างเช่น สมการที่สามข้างต้นหมายความว่า: "สำหรับฟังก์ชันใดๆ ที่สอดคล้องกับเอฟ(n)=โอ(1){\displaystyle f(n)=O(1)}มีฟังก์ชันบางอย่างจี(n)=โอ(อีn){\displaystyle g(n)=O(e^{n})}โดยที่nเอฟ(n)=จี(n){\displaystyle n^{f(n)}=g(n)}"ค่าคงที่โดยนัยในประโยค "จี(n)=โอ(อีn){\displaystyle g(n)=O(e^{n})}"อาจขึ้นอยู่กับค่าคงที่โดยนัยในนิพจน์"เอฟ(n)=โอ(1){\displaystyle f(n)=O(1)}".

ตัวอย่างเพิ่มเติม: เอฟ=โอ(จี)⇒∫เอขเอฟ=โอ(∫เอขจี)เอฟ(x)=จี(x)+โอ(1)⇒อีเอฟ(x)=โอ(อีจี(x))(1+โอ(1/x))โอ(x)=โอ(1) สำหรับ x>0บาป⁡x=โอ(|x|) สำหรับความจริงทั้งหมด x.{\displaystyle {\begin{aligned}f=O(g)\;&\Rightarrow \;\int _{a}^{b}f=O{\bigg (}\int _{a}^{b}g{\bigg )}\\f(x)=g(x)+O(1)\;&\Rightarrow \;e^{f(x)}=O(e^{g(x)})\\(1+O(1/x))^{O(x)}&=O(1)\quad {\text{ for }}x>0\\\sin x&=O(|x|)\quad {\text{ for all real }}x.\end{aligned}}}

≫ ของ Vinogradov และ Ω ขนาดใหญ่ของ Knuth

เมื่อไรเอฟ,จี{\displaystyle f,g}ทั้งสองเป็นฟังก์ชันบวก Vinogradov [ 6 ]ได้แนะนำสัญกรณ์เอฟ(x)≫จี(x){\displaystyle f(x)\gg g(x)}ซึ่งหมายความเหมือนกับจี(x)=โอ(เอฟ(x)){\displaystyle g(x)=O(f(x))}สัญลักษณ์ทั้งสองของวินอกราดอฟมีความสมมาตรทางสายตา เช่นเดียวกับฟังก์ชันบวกเอฟ,จี{\displaystyle f,g}เรามี เอฟ(x)≪จี(x)⟺จี(x)≫เอฟ(x).{\displaystyle f(x)\ll g(x)\Longleftrightarrow g(x)\gg f(x).}

ในปี พ.ศ. 2519 Donald Knuth [ 8 ] ได้กำหนด

เอฟ(x)=Ω(จี(x))⟺จี(x)=โอ(เอฟ(x)){\displaystyle f(x)=\Omega (g(x))\Longleftrightarrow g(x)=O(f(x))}

ซึ่งมีความหมายเหมือนกับของวินอกราดอฟเอฟ(x)≫จี(x){\displaystyle f(x)\gg g(x)}.

อย่างไรก็ตาม ก่อนหน้านั้น Hardy และ Littlewood [ 7 ]ได้กำหนดไว้ว่าΩ{\displaystyle \Omega }แตกต่างกันและสัญลักษณ์ของพวกเขายังคงใช้กันอย่างแพร่หลายในทฤษฎีจำนวนเชิงวิเคราะห์ในปัจจุบัน[ 13 ] [ 11 ] [ 12 ] การให้เหตุผลในการใช้ของเขาΩ{\displaystyle \Omega }-สัญลักษณ์เพื่ออธิบายคุณสมบัติที่แข็งแกร่งกว่า[ 8 ] Knuth เขียนว่า: "สำหรับแอปพลิเคชันทั้งหมดที่ฉันเคยเห็นในวิทยาศาสตร์คอมพิวเตอร์ ข้อกำหนดที่แข็งแกร่งกว่า ... เหมาะสมกว่ามาก" Knuth ยังเขียนเพิ่มเติมว่า "แม้ว่าฉันจะเปลี่ยนคำจำกัดความของ Hardy และ Littlewood ของΩ{\displaystyle \Omega }ฉันรู้สึกว่ามีเหตุผลที่จะทำเช่นนั้นเพราะคำจำกัดความของพวกเขาไม่ได้ถูกนำมาใช้อย่างแพร่หลาย และเพราะมีวิธีอื่นที่จะพูดในสิ่งที่พวกเขาต้องการจะพูดในกรณีที่ค่อนข้างหายากเมื่อคำจำกัดความของพวกเขาใช้ได้” [ 8 ]สิ่งสำคัญของ KnuthΩ{\displaystyle \Omega }ปัจจุบันมีการใช้งานอย่างแพร่หลายในสาขาวิทยาการคอมพิวเตอร์และคณิตศาสตร์เชิงการจัดเรียง

≍ ของฮาร์ดี้และ Θ ตัวใหญ่ของคนูธ

ในทฤษฎีจำนวนเชิงวิเคราะห์[ 12 ]สัญลักษณ์เอฟ(x)≍จี(x){\displaystyle f(x)\asymp g(x)}หมายถึงทั้งสอง เอฟ(x)=โอ(จี(x)){\displaystyle f(x)=O(g(x))}และจี(x)=โอ(เอฟ(x)){\displaystyle g(x)=O(f(x))}. สัญลักษณ์นี้เดิมทีเป็นของ Hardy [ 5 ]สัญลักษณ์ของ Knuth สำหรับแนวคิดเดียวกันคือเอฟ(x)=Θ(จี(x)){\displaystyle f(x)=\Theta (g(x))}[ 8 ] โดยคร่าวๆ แล้วข้อความเหล่านี้ยืนยันว่าเอฟ(x){\displaystyle f(x)}และจี(x){\displaystyle g(x)}มีลำดับเดียวกันสัญลักษณ์เหล่านี้หมายความว่ามีค่าคงที่ที่เป็นบวกเอ็ม,เอ็น{\displaystyle M,N} ดังนั้น เอ็นจี(x)≤เอฟ(x)≤เอ็มจี(x){\displaystyle Ng(x)\leq f(x)\leq Mg(x)} สำหรับทุกคนx{\displaystyle x}ในโดเมนทั่วไปของ เอฟ,จี{\displaystyle f,g}เมื่อฟังก์ชันถูกกำหนดบนจำนวนเต็มบวกหรือจำนวนจริงบวก เช่นเดียวกับบิ๊กโอ ผู้เขียนมักจะตีความข้อความต่างๆ เอฟ(x)=Ω(จี(x)){\displaystyle f(x)=\Omega (g(x))}และเอฟ(x)=Θ(จี(x)){\displaystyle f(x)=\Theta (g(x))}โดยยึดถือสำหรับทุกสิ่งที่มีขนาดใหญ่เพียงพอx{\displaystyle x}นั่นคือสำหรับทุกคนx{\displaystyle x}เกินกว่าจุดหนึ่งx0{\displaystyle x_{0}}บางครั้งอาจระบุโดยการเพิ่มคำต่อท้ายx→∞{\displaystyle x\to \infty }ต่อข้อความนั้น ตัวอย่างเช่น 2n2−10n=Θ(n2){\displaystyle 2n^{2}-10n=\Theta (n^{2})} เป็นจริงสำหรับโดเมนn≥6{\displaystyle n\geq 6}แต่จะเป็นเท็จหากโดเมนเป็นจำนวนเต็มบวกทั้งหมด เนื่องจากฟังก์ชันจะมีค่าเป็นศูนย์ที่โดเมนเหล่านั้นn=5{\displaystyle n=5}.

ตัวอย่างเพิ่มเติม

n3+20n2+n+12≍n3 สำหรับทุกคน n≥1.{\displaystyle n^{3}+20n^{2}+n+12\asymp n^{3}\quad {\text{ for all }}n\geq 1.}

(1+x)8=x8+Θ(x7) สำหรับทุกคน x≥1.{\displaystyle (1+x)^{8}=x^{8}+\Theta (x^{7})\quad {\text{ for all }}x\geq 1.}

สัญลักษณ์

เอฟ(n)=อีΩ(n) สำหรับทุกคน n≥1,{\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,} หมายความว่ามีค่าคงที่ที่เป็นบวกเอ็ม{\displaystyle M} ดังนั้นเอฟ(n)≥อีเอ็มn{\displaystyle f(n)\geq e^{Mn}}สำหรับทุกคนn≥1{\displaystyle n\geq 1}ในทางตรงกันข้าม เอฟ(n)=อี−โอ(n) สำหรับทุกคน n≥1,{\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,} หมายความว่ามีค่าคงที่ที่เป็นบวกเอ็ม{\displaystyle M} ดังนั้นเอฟ(n)≥อี−เอ็มn{\displaystyle f(n)\geq e^{-Mn}}สำหรับทุกคนn≥1{\displaystyle n\geq 1}และ เอฟ(n)=อีΘ(n) สำหรับทุกคน n≥1,{\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,} หมายความว่ามีค่าคงที่ที่เป็นบวกเอ็ม,เอ็น{\displaystyle M,N} ดังนั้นอีเอ็มn≤เอฟ(n)≤อีเอ็นn{\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}สำหรับทุกคนn≥1{\displaystyle n\geq 1}.

สำหรับโดเมนใดๆดี{\displaystyle D}, เอฟ(x)=จี(x)+โอ(1)⟺อีเอฟ(x)≍อีจี(x),{\displaystyle f(x)=g(x)+O(1)\Longleftrightarrow e^{f(x)}\asymp e^{g(x)},} แต่ละข้อความมีไว้สำหรับทุกคนx{\displaystyle x}ในดี{\displaystyle D}.

ลำดับของฟังก์ชันทั่วไป

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

สัญกรณ์ชื่อตัวอย่าง
โอ(1){\displaystyle O(1)}คงที่การหาค่ามัธยฐานของชุดตัวเลขที่เรียงลำดับแล้ว; การคำนวณ(−1)n{\displaystyle (-1)^{n}}การใช้ ตารางค้นหาที่มีขนาดคงที่
โอ(α(n)){\displaystyle O(\alpha (n))}ฟังก์ชัน Ackermann ผกผันความซับซ้อนเฉลี่ยต่อการดำเนินการสำหรับโครงสร้างข้อมูลเซตที่ไม่เกี่ยวข้องกัน
โอ(บันทึก⁡บันทึก⁡n){\displaystyle O(\log \log n)}ลอการิทึมคู่จำนวนครั้งเฉลี่ยของการเปรียบเทียบที่ใช้ในการค้นหารายการโดยใช้การค้นหาแบบแทรกสอดในอาร์เรย์ที่เรียงลำดับแล้วซึ่งกระจายอย่างสม่ำเสมอ
โอ(บันทึก⁡n){\displaystyle O(\log n)}ลอการิทึมการค้นหารายการในอาร์เรย์ที่เรียงลำดับแล้วด้วยการค้นหาแบบไบนารี หรือ ต้นไม้ค้นหาแบบสมดุลตลอดจนการดำเนินการทั้งหมดในฮีปแบบไบโนเมียล
โอ((บันทึก⁡n)ซี){\displaystyle O((\log n)^{c})}ซี>1{\textstyle c>1}โพลีลอการิทมิกการเรียงลำดับเมทริกซ์แบบลูกโซ่สามารถแก้ไขได้ในเวลาแบบพหุลอการิทึมบนเครื่องเข้าถึงแบบสุ่มขนาน
โอ(nซี){\displaystyle O(n^{c})}0<ซี<1{\textstyle 0<c<1}กำลังเศษส่วนการค้นหาในต้นไม้ kd การทดสอบความเป็นจำนวนเฉพาะแบบง่าย โดยการหารแบบทดลอง (โอ(n){\displaystyle O({\sqrt {n}})})
โอ(n){\displaystyle O(n)}เชิงเส้นการค้นหารายการในรายการที่ไม่เรียงลำดับหรือในอาร์เรย์ที่ไม่เรียงลำดับ การบวก จำนวนเต็ม nบิตสองจำนวนโดยใช้การทดแบบระลอกคลื่น
โอ(nบันทึก*⁡n){\displaystyle O(n\log ^{*}n)}n log-star nดำเนินการสร้างสามเหลี่ยมของรูปหลายเหลี่ยมอย่างง่ายโดยใช้อัลกอริทึมของ Seidel [ 14 ]โดยที่บันทึก*⁡(n)={0,ถ้า n≤11+บันทึก*⁡(บันทึก⁡n),ถ้า n>1{\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}
โอ(nบันทึก⁡n)=โอ(บันทึก⁡n!){\displaystyle O(n\log n)=O(\log n!)}แบบเชิงเส้น แบบลอการิทึมเชิงเส้น แบบกึ่งเชิงเส้น หรือ "nบันทึก⁡n{\displaystyle n\log n}"การแปลงฟูริเยร์แบบเร็ว (Fast Fourier Transform) ; การเรียงลำดับแบบเปรียบเทียบ ที่เร็วที่สุดเท่าที่จะเป็นไปได้ ; การเรียงลำดับ แบบฮีปซอร์ตและการเรียงลำดับแบบผสาน (Merge Sort)
โอ(n2){\displaystyle O(n^{2})}กำลังสองการคูณสองn{\displaystyle n}-จำนวนหลักโดย การคูณตาม ตำราเรียน ; อัลกอริทึมการเรียงลำดับแบบง่าย เช่น บับ เบิลซอร์ต (bubble sort) , ซีเล็คชั่นซอร์ต (selection sort ) และ อินเสิร์ชั่นซอร์ต ( insertion sort ); ขอบเขต (กรณีที่เลวร้ายที่สุด) ของอัลกอริทึมการเรียงลำดับที่เร็วกว่า เช่นควิกซอร์ต (quicksort) , เชลล์ซอร์ต (Shellsort)และทรีซอร์ต (tree sort)
โอ(nซี){\displaystyle O(n^{c})}พหุนามหรือพีชคณิตการวิเคราะห์ ไวยากรณ์แบบเชื่อมต่อต้นไม้ ; การจับคู่สูงสุดสำหรับกราฟสองส่วน ; การหาดีเทอร์มิแนนต์ด้วยการแยกส่วน LU
แอลn[α,ซี]=อี(ซี+โอ(1))(ln⁡n)α(ln⁡ln⁡n)1−α{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}0<α<1{\textstyle 0<\alpha <1}สัญกรณ์ Lหรือเลขชี้กำลังย่อยการแยกตัวประกอบของจำนวนโดยใช้ตะแกรงกำลังสองหรือตะแกรงสนามจำนวน
โอ(ซีn){\displaystyle O(c^{n})}ซี>1{\textstyle c>1}เลขชี้กำลังการหาคำตอบ (ที่แน่นอน) ของปัญหาพนักงานขายเดินทางโดยใช้การเขียนโปรแกรมเชิงพลวัตการตรวจสอบว่าข้อความตรรกะสองข้อความนั้นเทียบเท่ากันหรือไม่โดยใช้การค้นหาแบบบรูทฟอร์ซ
โอ(n!){\displaystyle O(n!)}แฟกทอเรียลการแก้ปัญหาพนักงานขายเดินทางโดยใช้การค้นหาแบบบรูทฟอร์ซ การสร้างการเรียงสับเปลี่ยนแบบไม่จำกัดทั้งหมด ของ เซต ลำดับบางส่วน การหาดีเทอร์มิแนนต์ด้วยการกระจายลาปลาสการแจงนับพาร์ติชันทั้งหมดของเซต

คำแถลงเอฟ(n)=โอ(n!){\displaystyle f(n)=O(n!)}บางครั้งอาจอ่อนลงเอฟ(n)=โอ(nn){\displaystyle f(n)=O\left(n^{n}\right)}เพื่อหาอนุพันธ์ของสูตรที่ง่ายกว่าสำหรับความซับซ้อนเชิงอะซิมโทติก ในตัวอย่างเหล่านี้หลายๆ ตัวอย่าง เวลาในการทำงานจริงคือΘ(จี(n)){\displaystyle \Theta (g(n))}ซึ่งให้ความแม่นยำยิ่งขึ้น

สัญกรณ์ลิตเติลโอ

สำหรับฟังก์ชันค่าจริงหรือค่าเชิงซ้อนของตัวแปรจริง x{\displaystyle x}กับจี(x)>0{\displaystyle g(x)>0}สำหรับขนาดที่ใหญ่พอสมควรx{\displaystyle x}หนึ่งเขียนว่า [ 2 ]

เอฟ(x)=โอ(จี(x)) เช่น x→∞{\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to \infty }

ถ้า ลิมx→∞เอฟ(x)จี(x)=0.{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=0.} กล่าวคือ สำหรับค่าคงที่บวกε ทุกค่า จะมีค่าคงที่อยู่ค่าหนึ่งx0{\displaystyle x_{0}}โดยที่

|เอฟ(x)|≤εจี(x) สำหรับทุกคน x≥x0.{\displaystyle |f(x)|\leq \varepsilon g(x)\quad {\text{ for all }}x\geq x_{0}.}

โดยสัญชาตญาณแล้ว นี่หมายความว่าจี(x){\displaystyle g(x)}เติบโตเร็วกว่ามากเอฟ(x){\displaystyle f(x)}หรือเทียบเท่าเอฟ(x){\displaystyle f(x)}เติบโตช้ากว่ามาก จี(x){\displaystyle g(x)}ตัวอย่างเช่น คนเรามี

200x=โอ(x2){\displaystyle 200x=o(x^{2})}และ1/x=โอ(1),{\displaystyle 1/x=o(1),}  ทั้งสองอย่างx→∞.{\displaystyle x\to \infty .}

เมื่อเราสนใจพฤติกรรมของฟังก์ชันสำหรับค่าขนาดใหญ่ของx{\displaystyle x}สัญกรณ์ little-o สื่อความหมายได้ชัดเจนกว่าสัญกรณ์ big-o ที่สอดคล้องกัน กล่าวคือ ทุกฟังก์ชันที่เป็น little-o ของจี{\displaystyle g}ยังเป็นบิ๊กโอของจี{\displaystyle g}ในช่วงเวลาหนึ่ง[เอ,∞){\displaystyle [a,\infty )}แต่ไม่ใช่ทุกฟังก์ชันที่เป็นบิ๊กโอจี{\displaystyle g}เป็นลิตเติ้ลโอของจี{\displaystyle g}. ตัวอย่างเช่น,2x2=โอ(x2){\displaystyle 2x^{2}=O(x^{2})}แต่2x2≠โอ(x2){\displaystyle 2x^{2}\neq o(x^{2})}สำหรับx≥1{\displaystyle x\geq 1}.

Little-o รองรับการดำเนินการทางคณิตศาสตร์หลายอย่าง ตัวอย่างเช่น

ถ้าซี{\displaystyle c}เป็นค่าคงที่ที่ไม่เป็นศูนย์ และเอฟ=โอ(จี){\displaystyle f=o(g)}แล้วซี⋅เอฟ=โอ(จี){\displaystyle c\cdot f=o(g)}, และ
ถ้าเอฟ=โอ(เอฟ){\displaystyle f=o(F)}และจี=โอ(จี){\displaystyle g=o(G)}แล้วเอฟ⋅จี=โอ(เอฟ⋅จี).{\displaystyle f\cdot g=o(F\cdot G).}
ถ้าเอฟ=โอ(เอฟ){\displaystyle f=o(F)}และจี=โอ(จี){\displaystyle g=o(G)}แล้วเอฟ+จี=โอ(เอฟ+จี){\displaystyle f+g=o(F+G)}

นอกจากนี้ยังสอดคล้องกับ ความสัมพันธ์ แบบถ่ายทอดได้ อีกด้วย :

ถ้าเอฟ=โอ(จี){\displaystyle f=o(g)}และจี=โอ(ชม.){\displaystyle g=o(h)}แล้วเอฟ=โอ(ชม.).{\displaystyle f=o(h).}

Little-o ยังสามารถขยายไปสู่กรณีจำกัดได้อีกด้วย: [ 2 ]เอฟ(x)=โอ(จี(x)) เช่น x→x0{\displaystyle f(x)=o(g(x))\quad {\text{ as }}x\to x_{0}}ถ้า ลิมx→x0เอฟ(x)จี(x)=0.{\displaystyle \lim _{x\to x_{0}}{\frac {f(x)}{g(x)}}=0.} กล่าวอีกนัยหนึ่งคือ เอฟ(x)=α(x)จี(x){\displaystyle f(x)=\alpha (x)g(x)}สำหรับบางคนα(x){\displaystyle \alpha (x)}กับลิมx→x0α(x)=0{\displaystyle \lim _{x\to x_{0}}\alpha (x)=0}.

คำจำกัดความนี้มีประโยชน์อย่างยิ่งในการคำนวณลิมิตโดยใช้ชุดอนุกรมเทย์เลอร์ตัวอย่างเช่น:

บาป⁡x=x−x33!+…=x+โอ(x2) เช่น x→0{\displaystyle \sin x=x-{\frac {x^{3}}{3!}}+\ldots =x+o(x^{2}){\text{ as }}x\to 0}, ดังนั้นลิมx→0บาป⁡xx=ลิมx→0x+โอ(x2)x=ลิมx→01+โอ(x)=1{\displaystyle \lim _{x\to 0}{\frac {\sin x}{x}}=\lim _{x\to 0}{\frac {x+o(x^{2})}{x}}=\lim _{x\to 0}1+o(x)=1}

สัญกรณ์เชิงอะซิมโทติก

ความสัมพันธ์ที่เกี่ยวข้องกับ little-o คือสัญกรณ์ เชิงอะซิมโทติก~{\displaystyle \sim }สำหรับฟังก์ชันค่าจริงเอฟ,จี{\displaystyle f,g}การแสดงออกเอฟ(x)~จี(x) เช่น x→∞{\displaystyle f(x)\sim g(x)\quad {\text{ as }}x\to \infty } วิธี ลิมx→∞เอฟ(x)จี(x)=1.{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=1.} เราสามารถเชื่อมโยงสิ่งนี้เข้ากับ little-o ได้โดยสังเกตว่า เอฟ(x)~จี(x){\displaystyle f(x)\sim g(x)}เทียบเท่ากับ เอฟ(x)=(1+โอ(1))จี(x){\displaystyle f(x)=(1+o(1))g(x)}. ที่นี่โอ(1){\displaystyle o(1)}หมายถึงฟังก์ชันที่มีแนวโน้มเข้าสู่ศูนย์เมื่อx→∞{\displaystyle x\to \infty }อ่านได้ว่า "เอฟ(x){\displaystyle f(x)}เป็นค่าประมาณเชิงเส้นกำกับของจี(x){\displaystyle g(x)}สำหรับฟังก์ชันที่ไม่เป็นศูนย์บนโดเมนเดียวกัน (จำกัดหรืออนันต์)~{\displaystyle \sim }ก่อให้เกิด ความ สัมพันธ์สมมูล

หนึ่งในทฤษฎีบทที่มีชื่อเสียงที่สุดที่ใช้สัญลักษณ์นี้ ~{\displaystyle \sim }คือสูตรของสเตอร์ลิงn!~(nอี)n2πn เช่น n→∞.{\displaystyle n!\sim {\bigg (}{\frac {n}{e}}{\bigg )}^{n}{\sqrt {2\pi n}}\quad {\text{ as }}n\to \infty .} ในทฤษฎีจำนวนทฤษฎีบทจำนวนเฉพาะอัน โด่งดัง กล่าวไว้ว่า π(x)~xบันทึก⁡x เช่น x→∞,{\displaystyle \pi (x)\sim {\frac {x}{\log x}}\quad {\text{ as }}x\to \infty ,} ที่ไหนπ(x){\displaystyle \pi (x)}คือจำนวนของจำนวนเฉพาะซึ่งไม่เกินx{\displaystyle x}และบันทึก{\displaystyle \log }คือ ลอการิทึมธรรมชาติของx{\displaystyle x}.

เช่นเดียวกับ little-o ก็มีเวอร์ชันที่มีขอบเขตจำกัด (แบบสองด้านหรือแบบด้านเดียว ) ด้วยเช่นกัน ตัวอย่างเช่น บาป⁡x~x เช่น x→0.{\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}

ตัวอย่างเพิ่มเติม: xเอ=โอเอ,ข(อีขx) เช่น x→∞, สำหรับค่าคงที่บวกใดๆ เอ,ข,{\displaystyle x^{a}=o_{a,b}(e^{bx})\quad {\text{ as }}x\to \infty ,{\text{ for any positive constants }}a,b,}เอฟ(x)=จี(x)+โอ(1)⟺อีเอฟ(x)~อีจี(x)(x→∞).{\displaystyle f(x)=g(x)+o(1)\quad \Longleftrightarrow \quad e^{f(x)}\sim e^{g(x)}\quad (x\to \infty ).}∑n=1∞1nส~1ส−1(ส→1+).{\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (s\to 1^{+}).} เส้นกำกับสุดท้ายเป็นคุณสมบัติพื้นฐานของ ฟังก์ชันซีตาของรีมันน์

𝜔 เล็กๆ ของ Knuth

สำหรับฟังก์ชันที่มีค่าเป็นบวกและเป็นจริงในที่สุดเอฟ,จี,{\displaystyle f,g,}สัญลักษณ์ เอฟ(x)=ω(จี(x)) เช่น x→∞{\displaystyle f(x)=\omega (g(x))\quad {\text{ as }}x\to \infty } วิธี ลิมx→∞เอฟ(x)จี(x)=∞.{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{g(x)}}=\infty .} กล่าวอีกนัยหนึ่งคือจี(x)=โอ(เอฟ(x)){\displaystyle g(x)=o(f(x))}โดยคร่าวๆ แล้ว หมายความว่าเอฟ(x){\displaystyle f(x)} เติบโตเร็วกว่ามากจี(x){\displaystyle g(x)}.

สัญกรณ์ Ω ของ Hardy–Littlewood

ในปี ค.ศ. 1914 จี.เอช. ฮาร์ดีและเจ.อี. ลิตเติลวูดได้นำเสนอสัญลักษณ์ใหม่ Ω,{\displaystyle \ \Omega ,}[ 7 ]ซึ่งกำหนดไว้ดังนี้:

เอฟ(x)=Ω(จี(x)){\displaystyle f(x)=\Omega (g(x))\quad }เช่นx→∞{\displaystyle \quad x\to \infty \quad }ถ้าลิม ซัพx→∞ | เอฟ(x) จี(x)|>0 .{\displaystyle \quad \limsup _{x\to \infty }\ \left|{\frac {\ f(x)\ }{g(x)}}\right|>0~.}

ดังนั้น เอฟ(x)=Ω(จี(x)) {\displaystyle ~f(x)=\Omega (g(x))~}คือการปฏิเสธของ เอฟ(x)=โอ(จี(x)) .{\displaystyle ~f(x)=o(g(x))~.}

ในปี ค.ศ. 1916 ผู้เขียนกลุ่มเดียวกันนี้ได้นำเสนอสัญลักษณ์ใหม่สองแบบ Ωอาร์ {\displaystyle \ \Omega _{R}\ }และ Ωแอล ,{\displaystyle \ \Omega _{L}\ ,}กำหนดไว้ดังนี้: [ 15 ]

เอฟ(x)=Ωอาร์(จี(x)){\displaystyle f(x)=\Omega _{R}(g(x))\quad }เช่นx→∞{\displaystyle \quad x\to \infty \quad }ถ้าลิม ซัพx→∞  เอฟ(x) จี(x)>0 ;{\displaystyle \quad \limsup _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}>0\ ;}
เอฟ(x)=Ωแอล(จี(x)){\displaystyle f(x)=\Omega _{L}(g(x))\quad }เช่นx→∞{\displaystyle \quad x\to \infty \quad }ถ้า ลิม อินฟ์x→∞  เอฟ(x) จี(x)<0 .{\displaystyle \quad ~\liminf _{x\to \infty }\ {\frac {\ f(x)\ }{g(x)}}<0~.}

สัญลักษณ์เหล่านี้ถูกใช้โดยE. Landauโดยมีความหมายเดียวกันในปี พ.ศ. 2467 [ 16 ]อย่างไรก็ตาม ผู้เขียนที่ตาม Landau ใช้สัญลักษณ์ที่แตกต่างกันสำหรับคำจำกัดความเดียวกัน: [ 11 ]สัญลักษณ์ Ωอาร์ {\displaystyle \ \Omega _{R}\ }ได้ถูกแทนที่ด้วยสัญลักษณ์ปัจจุบันแล้ว Ω+ {\displaystyle \ \Omega _{+}\ }ด้วยคำจำกัดความเดียวกัน และ Ωแอล {\displaystyle \ \Omega _{L}\ }กลายเป็น Ω− .{\displaystyle \ \Omega _{-}~.}

สัญลักษณ์ทั้งสามนี้ Ω ,Ω+ ,Ω− ,{\displaystyle \ \Omega \ ,\Omega _{+}\ ,\Omega _{-}\ ,}รวมถึง เอฟ(x)=Ω±(จี(x)) {\displaystyle \ f(x)=\Omega _{\pm }(g(x))\ }(หมายความว่า เอฟ(x)=Ω+(จี(x)) {\displaystyle \ f(x)=\Omega _{+}(g(x))\ }และ เอฟ(x)=Ω−(จี(x)) {\displaystyle \ f(x)=\Omega _{-}(g(x))\ }(ทั้งสองอย่างพึงพอใจ) ปัจจุบันถูกนำมาใช้ในทฤษฎีจำนวนเชิงวิเคราะห์[ 11 ] [ 12 ]

ตัวอย่างง่ายๆ

เรามี

บาป⁡x=Ω(1){\displaystyle \sin x=\Omega (1)\quad }เช่นx→∞ ,{\displaystyle \quad x\to \infty \ ,}

และแม่นยำยิ่งขึ้นไปอีก

บาป⁡x=Ω±(1){\displaystyle \sin x=\Omega _{\pm }(1)\quad }เช่นx→∞, {\displaystyle \quad x\to \infty ,~}

ที่ไหนΩ±{\displaystyle \Omega _{\pm }}หมายความว่าด้านซ้ายเป็นทั้งสองอย่างΩ+(1){\displaystyle \Omega _{+}(1)}และΩ−(1){\displaystyle \Omega _{-}(1)},

เรามี

1+บาป⁡x=Ω(1){\displaystyle 1+\sin x=\Omega (1)\quad }เช่นx→∞ ,{\displaystyle \quad x\to \infty \ ,}

และแม่นยำยิ่งขึ้นไปอีก

1+บาป⁡x=Ω+(1){\displaystyle 1+\sin x=\Omega _{+}(1)\quad }เช่นx→∞ ;{\displaystyle \quad x\to \infty \ ;}

อย่างไรก็ตาม

1+บาป⁡x≠Ω−(1){\displaystyle 1+\sin x\neq \Omega _{-}(1)\quad }เช่นx→∞ .{\displaystyle \quad x\to \infty ~.}

กลุ่มสัญลักษณ์ Bachmann–Landau

เพื่อทำความเข้าใจนิยามอย่างเป็นทางการ โปรดดู รายการสัญลักษณ์ตรรกศาสตร์ที่ใช้ในคณิตศาสตร์

สัญกรณ์ชื่อ[ 8 ]คำอธิบายคำจำกัดความอย่างเป็นทางการคำจำกัดความโดยย่อ

[ 4 ] [ 5 ] [ 8 ] [ 7 ] [ 17 ] [ 18 ]

เอฟ(n)=โอ(จี(n)){\displaystyle f(n)=O(g(n))}หรือ

เอฟ(n)≪จี(n){\displaystyle f(n)\ll g(n)}(สัญกรณ์ของวินอกราดอฟ)

บิ๊กโอ; บิ๊กโอ; บิ๊กโอไมครอน[ 8 ] [ b ]|เอฟ|{\displaystyle |f|}มีค่าสูงสุดจำกัดโดยg (โดยมีค่าคงที่ประกอบ)เค{\displaystyle k})∃เค>0∀n∈ดี:|เอฟ(n)|≤เคจี(n){\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)}จีบn∈ดี|เอฟ(n)|จี(n)<∞{\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty }
เอฟ(n)=โอ(จี(n)){\displaystyle f(n)=o(g(n))}โอเล็ก โอเล็ก โอเล็ก โอเล็กfถูกครอบงำโดยgในเชิงอะซิมโทติก (สำหรับปัจจัยคงที่ใดๆ)เค{\displaystyle k})∀เค>0∃n0∀n>n0:|เอฟ(n)|≤เคจี(n){\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}ลิมn→∞เอฟ(n)จี(n)=0{\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}
เอฟ(n)=Ω(จี(n)){\displaystyle f(n)=\Omega (g(n))}โอเมกาใหญ่ในทฤษฎีจำนวน (ฮาร์ดี้-ลิตเติลวูด)|เอฟ|{\displaystyle |f|}ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก∃เค>0∀n0∃n>n0:|เอฟ(n)|≥เคจี(n){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}ลิม ซัพn→∞|เอฟ(n)|จี(n)>0{\displaystyle \limsup _{n\to \infty }{\frac {|f(n)|}{g(n)}}>0}
เอฟ(n)=Ω+(จี(n)){\displaystyle f(n)=\Omega _{+}(g(n))}โอเมก้าพลัส (ฮาร์ดี้-ลิตเติลวูด)เอฟ{\displaystyle f}ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก∃เค>0∀n0∃n>n0:เอฟ(n)≥เคจี(n){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon f(n)\geq k\,g(n)}ลิม ซัพn→∞เอฟ(n)จี(n)>0{\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{g(n)}}>0}
เอฟ(n)=Ω−(จี(n)){\displaystyle f(n)=\Omega _{-}(g(n))}โอเมก้าลบ (ฮาร์ดี้-ลิตเติลวูด)−เอฟ{\displaystyle -f}ไม่ได้ถูกครอบงำโดยgในเชิงอะซิมโทติก∃เค>0∀n0∃n>n0:−เอฟ(n)≥เคจี(n){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon -f(n)\geq k\,g(n)}ลิม ซัพn→∞−เอฟ(n)จี(n)>0{\displaystyle \limsup _{n\to \infty }{\frac {-f(n)}{g(n)}}>0}
เอฟ(n)=Ω±(จี(n)){\displaystyle f(n)=\Omega _{\pm }(g(n))}โอเมก้าพลัสและลบไม่ใช่ทั้งสองอย่างเอฟ{\displaystyle f}ก็ไม่เช่นกัน−เอฟ{\displaystyle -f}ถูกครอบงำโดยgในเชิงอะซิมโทติกเอฟ(n)=Ω+(จี(n)){\displaystyle f(n)=\Omega _{+}(g(n))}และเอฟ(n)=Ω−(จี(n)){\displaystyle f(n)=\Omega _{-}(g(n))}
เอฟ(n)≍จี(n){\displaystyle f(n)\asymp g(n)}(สัญลักษณ์ของฮาร์ดี้) หรือเอฟ(n)=Θ(จี(n)){\displaystyle f(n)=\Theta (g(n))}(สัญกรณ์แบบคนุท)อยู่ในลำดับเดียวกันกับ (ฮาร์ดี้); บิ๊กเธต้า (คนุธ)fถูกจำกัดโดยgทั้งสองข้างต้น (โดยมีปัจจัยคงที่)เค2{\displaystyle k_{2}}) และด้านล่าง (โดยมีปัจจัยคงที่)เค1{\displaystyle k_{1}})∃เค1>0∃เค2>0∀n∈ดี:{\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon }เค1จี(n)≤เอฟ(n)≤เค2จี(n){\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}เอฟ(n)=โอ(จี(n)){\displaystyle f(n)=O(g(n))}และจี(n)=โอ(เอฟ(n)){\displaystyle g(n)=O(f(n))}
เอฟ(n)~จี(n){\displaystyle f(n)\sim g(n)}เช่นn→เอ{\displaystyle n\to a}, ที่ไหนเอ{\displaystyle a}มีค่าจำกัด∞{\displaystyle \infty }

หรือ−∞{\displaystyle -\infty }

ความสมมูลเชิงอะซิมโทติกfเท่ากับg ในเชิงอะซิมโทติก∀ε>0∃n0∀n>n0:|เอฟ(n)จี(n)−1|<ε{\displaystyle \forall \varepsilon >0\,\exists n_{0}\,\forall n>n_{0}\colon \left|{\frac {f(n)}{g(n)}}-1\right|<\varepsilon }(ในกรณีเอ=∞{\displaystyle a=\infty })ลิมn→เอเอฟ(n)จี(n)=1{\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1}
เอฟ(n)=Ω(จี(n)){\displaystyle f(n)=\Omega (g(n))}(สัญกรณ์ของ Knuth) หรือ

เอฟ(n)≫จี(n){\displaystyle f(n)\gg g(n)}(สัญกรณ์ของวินอกราดอฟ)

โอเมก้าตัวใหญ่ในทฤษฎีความซับซ้อน (Knuth)fมีขอบเขตล่างโดยgโดยมีค่าคงที่ประกอบอยู่ด้วย∃เค>0∀n∈ดี:เอฟ(n)≥เคจี(n){\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)}ข้อมูลn∈ดีเอฟ(n)จี(n)>0{\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0}
เอฟ(n)=ω(จี(n)){\displaystyle f(n)=\omega (g(n))}เช่นn→เอ{\displaystyle n\to a},

ที่ไหนเอ{\displaystyle a}สามารถมีขอบเขตจำกัดได้∞{\displaystyle \infty }หรือ−∞{\displaystyle -\infty }

โอเมก้าขนาดเล็ก; โอเมก้าน้อยfครอบงำgในเชิงอะซิมโทติก∀เค>0∃n0∀n>n0:เอฟ(n)>เคจี(n){\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}(สำหรับเอ=∞{\displaystyle a=\infty })ลิมn→เอเอฟ(n)จี(n)=∞{\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty }

นิยามของขีดจำกัดนั้นตั้งอยู่บนสมมติฐานจี(n)>0{\displaystyle g(n)>0}สำหรับ n{\displaystyle n}ในบริเวณใกล้เคียงกับขอบเขต เมื่อขอบเขตคือ∞{\displaystyle \infty }ซึ่งหมายความว่าจี(n)>0{\displaystyle g(n)>0}สำหรับขนาดที่ใหญ่พอสมควรn{\displaystyle n}.

วิทยาการคอมพิวเตอร์และคณิตศาสตร์เชิงการจัดเรียงใช้หลักการขนาดใหญ่โอ{\displaystyle O}ธีต้าตัวใหญ่Θ{\displaystyle \Theta }, เล็กน้อยโอ{\displaystyle o}โอเมก้าน้อยω{\displaystyle \omega }และโอเมก้าขนาดใหญ่ของคนูธΩ{\displaystyle \Omega }สัญกรณ์ [ 3 ] ทฤษฎีจำนวนเชิงวิเคราะห์มักใช้ขนาดใหญ่โอ{\displaystyle O}, เล็กโอ{\displaystyle o}ฮาร์ดี้≍{\displaystyle \asymp }โอเมก้าตัวใหญ่ของฮาร์ดี้-ลิตเติลวูดΩ{\displaystyle \Omega }(โดยมีหรือไม่มีเครื่องหมาย +, − หรือ ± กำกับ) ของวินอกราดอฟ≪{\displaystyle \ll }และ≫{\displaystyle \gg }เครื่องหมายและ~{\displaystyle \sim }สัญกรณ์ [ 11 ] [ 4 ] [ 12 ] โอเมกาตัวเล็กω{\displaystyle \omega }สัญกรณ์ไม่ได้ถูกใช้บ่อยนักในการวิเคราะห์หรือในทฤษฎีจำนวน [ 19 ]

คุณภาพของการประมาณค่าโดยใช้สัญลักษณ์ที่แตกต่างกัน

โดยทั่วไป โดยเฉพาะในสาขาวิทยาการคอมพิวเตอร์ สิ่งสำคัญคือ...โอ{\displaystyle O}สัญลักษณ์นี้มักถูกนำมาใช้ในลักษณะที่แตกต่างกันเล็กน้อยเพื่ออธิบาย ขอบเขต ที่แน่นหนา เชิงอะซิมโทติก โดยใช้บิ๊กเธต้าΘ{\displaystyle \Theta }สัญกรณ์อาจเหมาะสมกว่าในบริบทที่กำหนด[ 20 ] ตัวอย่างเช่น เมื่อพิจารณาฟังก์ชันที(n)=73n3+22n2+58{\displaystyle T(n)=73n^{3}+22n^{2}+58}โดยทั่วไปแล้วเงื่อนไขทั้งหมดต่อไปนี้เป็นที่ยอมรับได้ แต่โดยปกติแล้วเงื่อนไขที่เข้มงวดกว่า (เช่น ข้อ 2, 3 และ 4 ด้านล่าง) จะได้รับความนิยมมากกว่าเงื่อนไขที่หลวมกว่า (เช่น ข้อ 1 ด้านล่าง)

  1. ที(n)=โอ(n100){\displaystyle T(n)=O(n^{100})}
  2. ที(n)=โอ(n3){\displaystyle T(n)=O(n^{3})}
  3. ที(n)=Θ(n3){\displaystyle T(n)=\Theta (n^{3})}
  4. ที(n)~73n3{\displaystyle T(n)\sim 73n^{3}}เช่นn→∞{\displaystyle n\to \infty }.

แม้ว่าข้อความทั้งสามข้อจะเป็นความจริง แต่แต่ละข้อก็มีข้อมูลมากขึ้นเรื่อยๆ อย่างไรก็ตาม ในบางสาขา การใช้สัญลักษณ์ O ขนาดใหญ่ (หมายเลข 2 ในรายการด้านบน) จะถูกใช้บ่อยกว่าการใช้สัญลักษณ์ Theta ขนาดใหญ่ (หมายเลข 3 ในรายการด้านบน) ตัวอย่างเช่น ถ้าที(n){\displaystyle T(n)}แสดงถึงเวลาในการทำงานของอัลกอริธึมที่พัฒนาขึ้นใหม่สำหรับขนาดอินพุตn{\displaystyle n}ผู้คิดค้นและผู้ใช้งานอัลกอริทึมอาจมีแนวโน้มที่จะกำหนดขอบเขตบนของระยะเวลาที่ใช้ในการทำงานโดยไม่ระบุขอบเขตล่างหรือพฤติกรรมเชิงอะซิมโทติกอย่างชัดเจน

ส่วนขยายของสัญกรณ์ Bachmann–Landau

สัญลักษณ์อีกแบบหนึ่งที่บางครั้งใช้ในวิทยาการคอมพิวเตอร์คือโอ~{\displaystyle {\tilde {O}}}(อ่านว่าsoft-O ) ซึ่งซ่อนปัจจัยโพลีลอการิทึมไว้ มีคำจำกัดความสองแบบที่ใช้กันอยู่: ผู้เขียนบางคนใช้เอฟ(n)=โอ~(จี(n)){\displaystyle f(n)={\tilde {O}}(g(n))}ใช้เป็นคำย่อสำหรับเอฟ(n)=โอ(จี(n)บันทึกเค⁡n){\displaystyle f(n)=O(g(n)\log ^{k}n)}สำหรับบางคนเค{\displaystyle k}ในขณะที่บางคนใช้เป็นคำย่อสำหรับเอฟ(n)=โอ(จี(n)บันทึกเค⁡จี(n)){\displaystyle f(n)=O(g(n)\log ^{k}g(n))} [ 21 ] เมื่อ​จี(n){\displaystyle g(n)}เป็นพหุนามในn{\displaystyle n}ไม่มีความแตกต่างกัน อย่างไรก็ตาม คำจำกัดความแบบหลังทำให้เราสามารถกล่าวได้ว่า ตัวอย่างเช่นn2n=โอ~(2n){\displaystyle n2^{n}={\tilde {O}}(2^{n})}ในขณะที่คำจำกัดความก่อนหน้านี้อนุญาตให้บันทึกเค⁡n=โอ~(1){\displaystyle \log ^{k}n={\tilde {O}}(1)}สำหรับค่าคงที่ใดๆเค{\displaystyle k}ผู้เขียนบางคนเขียนO *เพื่อจุดประสงค์เดียวกันกับคำจำกัดความหลัง[ 22 ]โดยพื้นฐานแล้ว มันเป็นเวอร์ชันที่ไม่แม่นยำน้อยกว่าของ สัญกรณ์ O ขนาดใหญ่ โดยไม่สนใจปัจจัยลอการิทึมในอัตราการเติบโตของฟังก์ชัน เนื่องจากบันทึกเค⁡n=โอ(nε){\displaystyle \log ^{k}n=o(n^{\varepsilon })} สำหรับค่าคงที่ใดๆเค{\displaystyle k}และใดๆ ε>0{\displaystyle \varepsilon >0}ตัวประกอบลอการิทึมมีความสำคัญน้อยกว่าเลขยกกำลังมากn{\displaystyle n}และยิ่งไม่มีนัยสำคัญเมื่อเทียบกับเลขชี้กำลัง

นอกจากนี้สัญกรณ์Lถูกกำหนดดังนี้

แอลn[α,ซี]=อี(ซี+โอ(1))(ln⁡n)α(ln⁡ln⁡n)1−α,{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}

สะดวกสำหรับฟังก์ชันที่อยู่ระหว่างพหุนามและเลขชี้กำลังในแง่ของบันทึก⁡n{\displaystyle \log n}.

การขยายความไปสู่ฟังก์ชันที่รับค่าในปริภูมิเวกเตอร์ที่มีบรรทัดฐาน ใดๆ นั้น ทำได้ง่าย (โดยการแทนที่ค่าสัมบูรณ์ด้วยบรรทัดฐาน) โดยที่เอฟ{\displaystyle f}และจี{\displaystyle g}ไม่จำเป็นต้องรับค่าในพื้นที่เดียวกัน การขยายความไปสู่ฟังก์ชันจี{\displaystyle g}การรับค่าในกลุ่มโทโพโลยี ใดๆ ก็เป็นไปได้เช่นกัน"กระบวนการจำกัด"x→x0{\displaystyle x\to x_{0}}นอกจากนี้ยังสามารถขยายความได้โดยการแนะนำฐานตัวกรอง แบบใด ก็ได้ เช่น ไปยังเน็ต แบบมีทิศทางเอฟ{\displaystyle f}และจี{\displaystyle g}. เดอะโอ{\displaystyle o}สัญลักษณ์นี้สามารถใช้เพื่อกำหนดอนุพันธ์และความสามารถในการหาอนุพันธ์ในปริภูมิทั่วไปได้ และยังใช้เพื่อกำหนดความสมมูล (เชิงอะซิมโทติก) ของฟังก์ชันได้อีกด้วย

เอฟ~จี⟺(เอฟ−จี)∈โอ(จี){\displaystyle f\sim g\iff (f-g)\in o(g)}

ซึ่งเป็นความสัมพันธ์สมมูลและเป็นแนวคิดที่เข้มงวดกว่าความสัมพันธ์ "เอฟ{\displaystyle f}เป็นΘ(จี){\displaystyle \Theta (g)}จากเบื้องบน (ลดทอนเหลือ)ลิมเอฟ/จี=1{\displaystyle \lim f/g=1}ถ้าเอฟ{\displaystyle f}และจี{\displaystyle g}(เป็นฟังก์ชันค่าจริงบวก) ตัวอย่างเช่น2x=Θ(x){\displaystyle 2x=\Theta (x)}คือ แต่ 2x−x≠โอ(x){\displaystyle 2x-x\neq o(x)}.

ประวัติศาสตร์

ในปี ค.ศ. 1870 Paul du Bois-Reymond [ 9 ] ให้คำจำกัดความไว้เอฟ(x)≻ϕ(x){\displaystyle f(x)\succ \phi (x)},เอฟ(x)~ϕ(x){\displaystyle f(x)\sim \phi (x)}และเอฟ(x)≺ϕ(x){\displaystyle f(x)\prec \phi (x)} หมายถึง ตามลำดับ ลิมx→∞เอฟ(x)ϕ(x)=∞,ลิมx→∞เอฟ(x)ϕ(x)>0,ลิมx→∞เอฟ(x)ϕ(x)=0.{\displaystyle \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=\infty ,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}>0,\quad \lim _{x\to \infty }{\frac {f(x)}{\phi (x)}}=0.} สิ่งเหล่านี้ไม่ได้รับการยอมรับอย่างแพร่หลายและไม่ได้ใช้ในปัจจุบันแล้ว แบบแรกและแบบที่สามมีความสมมาตร:เอฟ(x)≺ϕ(x){\displaystyle f(x)\prec \phi (x)}หมายความว่าเหมือนกันกับϕ(x)≻เอฟ(x){\displaystyle \phi (x)\succ f(x)}ต่อมาแลนเดาได้อุปการะคุณ~{\displaystyle \sim }ด้วยคำจำกัดความที่แคบกว่าซึ่งขีดจำกัดของเอฟ(x)/ϕ(x){\displaystyle f(x)/\phi (x)}เท่ากับ 1.

สัญลักษณ์ O ถูกนำมาใช้ครั้งแรกโดยนักทฤษฎีจำนวนPaul Bachmannในปี 1894 ในเล่มที่สองของหนังสือAnalytische Zahlentheorie (" ทฤษฎีจำนวนเชิงวิเคราะห์ ") [ 1 ]นักทฤษฎีจำนวนEdmund Landauได้นำสัญลักษณ์นี้มาใช้ และด้วยเหตุนี้จึงได้รับแรงบันดาลใจให้แนะนำสัญลักษณ์ o ในปี 1909 [ 2 ]ดังนั้นทั้งสองจึงถูกเรียกว่าสัญลักษณ์ Landau สัญลักษณ์เหล่านี้ถูกนำมาใช้ในคณิตศาสตร์ประยุกต์ในช่วงทศวรรษ 1950 สำหรับการวิเคราะห์เชิงอะซิมโทติก[ 23 ] สัญลักษณ์Ω{\displaystyle \Omega }(ในความหมายว่า "ไม่ใช่o เล็กน้อย ของ") ได้รับการแนะนำในปี พ.ศ. 2457 โดย Hardy และ Littlewood [ 7 ] Hardy และ Littlewood ยังได้แนะนำด้านซ้ายและด้านขวาในปี พ.ศ. 2459 อีกด้วยΩ{\displaystyle \Omega }สัญลักษณ์Ωอาร์{\displaystyle \Omega _{R}},Ωแอล{\displaystyle \Omega _{L}}(ปัจจุบันมักใช้สัญลักษณ์ว่า)Ω+,Ω−{\displaystyle \Omega _{+},\Omega _{-}}). [ 15 ]นี้Ω{\displaystyle \Omega }สัญกรณ์นี้ถูกใช้กันอย่างแพร่หลายในทฤษฎีจำนวนตั้งแต่ทศวรรษ 1950 [ 13 ]

ฮาร์ดี้เป็นผู้แนะนำสัญลักษณ์เหล่านั้น≼{\displaystyle \preccurlyeq }และสนับสนุน Bois-Reymond≺{\displaystyle \prec }(รวมถึงสัญลักษณ์อื่นๆ ที่กล่าวถึงไปแล้ว) ในบทความปี 1910 ของเขาเรื่อง "ลำดับแห่งอนันต์" [ 5 ]แต่ใช้สัญลักษณ์เหล่านี้เพียงในบทความ 3 ฉบับ (1910–1913) ในบทความและหนังสือที่เหลืออีกเกือบ 400 ฉบับ เขาใช้สัญลักษณ์ Landau O และ o อย่างสม่ำเสมอ[ 24 ] สัญลักษณ์ของ Hardy≼{\displaystyle \preccurlyeq }และ≍−{\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }ไม่ได้ใช้งานอีกต่อไปแล้ว

สัญลักษณ์~{\displaystyle \sim }ถึงแม้ว่าจะเคยใช้มาก่อนด้วยความหมายที่แตกต่างกัน[ 9 ]แต่ Landau ได้ให้คำจำกัดความสมัยใหม่ในปี พ.ศ. 2452 [ 2 ]และ Hardy ในปี พ.ศ. 2453 [ 5 ]ในหน้าเดียวกัน Hardy ได้ให้คำจำกัดความของสัญลักษณ์≍{\displaystyle \asymp }, ที่ไหนเอฟ(x)≍จี(x){\displaystyle f(x)\asymp g(x)}หมายความว่าทั้งสองเอฟ(x)=โอ(จี(x)){\displaystyle f(x)=O(g(x))}และจี(x)=โอ(เอฟ(x)){\displaystyle g(x)=O(f(x))}พึงพอใจ สัญลักษณ์นี้ยังคงใช้ในทฤษฎีจำนวนเชิงวิเคราะห์[ 25 ] [ 12 ] ฮาร์ดีเสนอสัญลักษณ์นี้ด้วย≍−{\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }, ที่ไหนเอฟ≍−จี{\displaystyle f\mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} g}หมายความว่าเอฟ~เคจี{\displaystyle f\sim Kg}สำหรับค่าคงที่บางค่าเค≠0{\displaystyle K\not =0}(ซึ่งสอดคล้องกับสัญลักษณ์ของ Bois-Reymond)เอฟ~จี{\displaystyle f\sim g})

ในช่วงทศวรรษ 1930 Vinogradov [ 6 ]ได้ทำให้สัญลักษณ์นี้เป็นที่นิยมเอฟ(x)≪จี(x){\displaystyle f(x)\ll g(x)} และจี(x)≫เอฟ(x){\displaystyle g(x)\gg f(x)}ซึ่งทั้งสองอย่างหมายความว่า เอฟ(x)=โอ(จี(x)){\displaystyle f(x)=O(g(x))}. สัญลักษณ์นี้กลายเป็นมาตรฐานในทฤษฎีจำนวนเชิงวิเคราะห์[ 4 ]

ในทศวรรษ 1970 สัญลักษณ์ Big O ได้รับความนิยมในวงการวิทยาการคอมพิวเตอร์โดยDonald Knuthผู้เสนอสัญลักษณ์ที่แตกต่างออกไปเอฟ(x)=Θ(จี(x)){\displaystyle f(x)=\Theta (g(x))}สำหรับฮาร์ดี้เอฟ(x)≍จี(x){\displaystyle f(x)\asymp g(x)}และเสนอคำจำกัดความที่แตกต่างกันสำหรับสัญลักษณ์โอเมกาของ Hardy และ Littlewood [ 8 ]

เรื่องของสัญลักษณ์

ลูกศร

ในทางคณิตศาสตร์ นิพจน์เช่นx→∞{\displaystyle x\to \infty }บ่งชี้ถึงการมีอยู่ของขีดจำกัดในสัญกรณ์บิ๊กโอและสัญกรณ์ที่เกี่ยวข้อง Ω,Θ,≫,≪,≍{\displaystyle \Omega ,\Theta ,\gg ,\ll ,\asymp }ไม่มีข้อจำกัดโดยนัย ซึ่งแตกต่างจากlittle- o ~{\displaystyle \sim }และω{\displaystyle \omega }สัญลักษณ์ สัญลักษณ์เช่นเอฟ(x)=โอ(จี(x))(x→∞){\displaystyle f(x)=O(g(x))\;\;(x\to \infty )}อาจถือได้ว่าเป็นการใช้สัญลักษณ์ในทางที่ผิด

เครื่องหมายเท่ากับ

บางคนพิจารณาเอฟ(x)=โอ(จี(x)){\displaystyle f(x)=O(g(x))}นอกจากนี้ยังถือเป็นการใช้สัญลักษณ์ที่ผิดพลาดเนื่องจากการใช้เครื่องหมายเท่ากับอาจทำให้เข้าใจผิดได้ เพราะมันสื่อถึงความสมมาตรซึ่งประโยคนี้ไม่มี ดังที่เดอ บรูอินกล่าวไว้ว่าโอ(x)=โอ(x2){\displaystyle O(x)=O(x^{2})}เป็นความจริง แต่โอ(x2)=โอ(x){\displaystyle O(x^{2})=O(x)}ไม่ใช่[ 26 ] Knuthอธิบายข้อความดังกล่าวว่าเป็น "ความเท่าเทียมกันทางเดียว" เนื่องจากหากสามารถสลับข้างได้ "เราสามารถอนุมานสิ่งที่ไร้สาระได้ เช่น n=n2{\displaystyle n=n^{2}}จากอัตลักษณ์n=โอ(n2){\displaystyle n=O(n^{2})}และn2=โอ(n2){\displaystyle n^{2}=O(n^{2})}[ 27 ] ในจดหมายอีก ฉบับหนึ่ง Knuth ยังชี้ให้เห็นว่า[ 28 ]

เครื่องหมายเท่ากับไม่สมมาตรเมื่อเทียบกับสัญลักษณ์อื่นๆ [เช่น ในสัญลักษณ์นี้] ที่นักคณิตศาสตร์มักใช้เครื่องหมาย '=' เหมือนกับที่ใช้คำว่า 'is' ในภาษาอังกฤษ: อริสโตเติลเป็นมนุษย์ แต่คนๆ หนึ่งไม่จำเป็นต้องเป็นอริสโตเติลเสมอไป

ด้วยเหตุผลเหล่านี้ บางคนจึงสนับสนุนให้ใช้สัญลักษณ์เซตและเขียนแทนเอฟ(x)∈โอ(จี(x)){\displaystyle f(x)\in O(g(x))}อ่านว่า "เอฟ(x){\displaystyle f(x)}เป็นองค์ประกอบหนึ่งของโอ(จี(x)){\displaystyle O(g(x))}", หรือ "เอฟ(x){\displaystyle f(x)}อยู่ในชุด โอ(จี(x)){\displaystyle O(g(x))}- กำลังคิดถึง  โอ(จี(x)){\displaystyle O(g(x))}ในฐานะที่เป็นคลาสของฟังก์ชันทั้งหมด ชม.(x){\displaystyle h(x)}โดยที่ชม.(x)=โอ(จี(x)){\displaystyle h(x)=O(g(x))}[ 27 ]อย่างไรก็ตาม การใช้เครื่องหมายเท่ากับเป็นเรื่องปกติ[ 26 ] [ 27 ] และสะดวกกว่าในนิพจน์ที่ซับซ้อนกว่าในรูป แบบเอฟ(x)=จี(x)+โอ(ชม.(x))=โอ(เค(x)).{\displaystyle f(x)=g(x)+O(h(x))=O(k(x)).}

บันทึกของวินอกราดอฟ≪{\displaystyle \ll }และ≫{\displaystyle \gg }ซึ่งใช้กันอย่างแพร่หลายในทฤษฎีจำนวน [ 11 ] [ 4 ] [ 12 ] ไม่ประสบปัญหาข้อบกพร่องนี้ เนื่องจากแสดงให้เห็นชัดเจนยิ่งขึ้นว่า big-O บ่งชี้ถึงความไม่เท่าเทียมกันมากกว่าความเท่าเทียมกัน นอกจาก นี้ยังมีความสมมาตรที่สัญกรณ์ big-O ขาดไป:เอฟ(x)≪จี(x){\displaystyle f(x)\ll g(x)} หมายความว่าเหมือนกันกับจี(x)≫เอฟ(x){\displaystyle g(x)\gg f(x)}. ในคณิตศาสตร์เชิงการจัดเรียงและวิทยาศาสตร์คอมพิวเตอร์ ไม่ค่อยพบเห็นสัญลักษณ์เหล่านี้[ 3 ]

การจัดเรียงตัวอักษร

ตัวอักษร Big O จะพิมพ์เป็นตัวพิมพ์ใหญ่ " O " แบบตัวเอียง ดังตัวอย่างต่อไปนี้:โอ(n2){\displaystyle O(n^{2})}[ 29 ] [ 30 ]ในTeXจะสร้างโดยการพิมพ์ 'O' ภายในโหมดคณิตศาสตร์ ซึ่งแตกต่างจากสัญกรณ์ Bachmann–Landau ที่มีชื่อเป็นภาษากรีก ไม่จำเป็นต้องใช้สัญลักษณ์พิเศษ อย่างไรก็ตาม ผู้เขียนบางคนใช้รูปแบบการเขียนแบบลายมือโอ{\displaystyle {\mathcal {O}}}แทนที่จะเป็นเช่นนั้น[ 31 ] [ 32 ]

เดิมทีตัวอักษร O ขนาดใหญ่หมายถึง "ลำดับของ" ("Ordnung", Bachmann 1894) ดังนั้นจึงเป็นอักษรละติน ทั้ง Bachmann และ Landau ไม่เคยเรียกมันว่า "Omicron" สัญลักษณ์นี้ถูกมองโดย Knuth ในภายหลัง (1976) ว่าเป็น omicron ตัวพิมพ์ใหญ่[ 8 ] ซึ่งอาจหมายถึงคำจำกัดความของสัญลักษณ์Omega ของเขา ไม่ควรใช้เลขศูนย์

ดูเพิ่มเติม

เอกสารอ้างอิงและหมายเหตุ

  1. 1 2 บาคมันน์, พอล (1894) Analytische Zahlentheorie [ ทฤษฎีจำนวนเชิงวิเคราะห์] (ภาษาเยอรมัน) ฉบับที่ 2. ไลป์ซิก : ทอยบเนอร์
  2. 1 2 3 4 5 ลันเดา, เอ็ดมันด์ (1909) Handbuch der Lehre von der Verteilung der Primzahlen [ คู่มือเกี่ยวกับทฤษฎีการกระจายตัวของจำนวนเฉพาะ] (ในภาษาเยอรมัน) ไลป์ซิก : บีจี ทอยบเนอร์; พิมพ์ซ้ำเป็นสองเล่มในเล่มเดียวโดย Chelsea, 1974 โดยมีภาคผนวกโดย Dr. Paul T. Bateman หน้า59–63 . 
  3. 1 2 3 4 5 6 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2022). "การกำหนดลักษณะเวลาการทำงาน". บทนำสู่อัลกอริธึม ( ฉบับที่ 4). สำนักพิมพ์ MIT และ McGraw-Hill. ISBN  978-0-262-53091-0.
  4. 1 2 3 4 5 6 Iwaniec, Henryk ; Kowalski, Emmanuel (2004). ทฤษฎีจำนวนเชิงวิเคราะห์ . สมาคมคณิตศาสตร์อเมริกัน.
  5. 1 2 3 4 5 Hardy, GH (1910). ลำดับแห่งอนันต์: 'Infinitärcalcül' ของ Paul du Bois-Reymondสำนักพิมพ์มหาวิทยาลัยเคมบริดจ์หน้า2 
  6. 1 2 3 4 วิโนกราดอฟ, มัตเววิช (1934) "การประมาณการใหม่สำหรับG ( n )ในปัญหาของ Waring" Doklady Akademii Nauk SSSR (ภาษารัสเซีย) 5 ( 5– 6): 249– 253.
    แปลเป็นภาษาอังกฤษโดย:
    Vinogradov, Matveevič (1985). ผลงานคัดสรร / อีวาน มัตเววิช วินอกราดอฟ; จัดทำโดยสถาบันคณิตศาสตร์สเตคลอฟแห่งสถาบันวิทยาศาสตร์แห่งสหภาพโซเวียต เนื่องในโอกาสวันคล้ายวันเกิดครบรอบ 90 ปี Springer-Verlag.
  7. 1 2 3 4 5 Hardy, GH ; Littlewood, JE (1914). "ปัญหาบางประการของการประมาณไดโอแฟนไทน์: ตอนที่ 2 อนุกรมตรีโกณมิติที่เกี่ยวข้องกับ ฟังก์ชันθวงรี " Acta Mathematica . 37 : 225. doi : 10.1007/BF02401834 . เก็บถาวรจากต้นฉบับเมื่อ 2018-12-12 . สืบค้นเมื่อ2017-03-14 . 
  8. 1 2 3 4 5 6 7 8 9 10 Knuth, Donald (เมษายน–มิถุนายน 1976). "Big Omicron and big Omega and big Theta" . SIGACT News . 8 (2): 18– 24. doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
  9. 1 2 3บัวส์-เรย์มอนด์, พอล ดู (1870) “ซูร์ ลา ความยิ่งใหญ่ สัมพันธ์ เด อินฟินิส เด ฟองก์ชัน ” อันนาลี ดิ มาเตเมติกา . ซีรีส์ 2. 4 : 338– 353. ดอย : 10.1007/BF02420041 .
  10. ↑ Sipser, Michael (2012). บทนำสู่ทฤษฎีการคำนวณ ( ฉบับที่ 3). บอสตัน, แมสซาชูเซตส์: สำนักพิมพ์ PWS. 
  11. 1 2 3 4 5 6 Ivić, A. (1985). ฟังก์ชันซีตาของรีมันน์ . John Wiley & Sons. บทที่9. 
  12. 1 2 3 4 5 6 7 Gérald Tenenbaum, บทนำสู่ทฤษฎีจำนวนเชิงวิเคราะห์และความน่าจะเป็น, « สัญกรณ์ », หน้า xxiii. สมาคมคณิตศาสตร์อเมริกัน, พรอวิเดนซ์ รัฐโรดไอส์แลนด์, 2015.
  13. 1 2อี. ซี. ทิทช์มาร์ช, ทฤษฎีของฟังก์ชันซีตาของรีมันน์ (ออกซ์ฟอร์ด; สำนักพิมพ์แคลเรนดอน, 1951)
  14. ↑ Seidel, Raimund (1991), "อัลกอริทึมแบบสุ่มเพิ่มทีละขั้นที่ง่ายและรวดเร็วสำหรับการคำนวณการแบ่งรูปสี่เหลี่ยมคางหมูและการสร้างรูปสามเหลี่ยมของรูปหลายเหลี่ยม", เรขาคณิตเชิงคำนวณ , 1 : 51– 64, CiteSeerX 10.1.1.55.5877 , doi : 10.1016/0925-7721(91)90012-4 
  15. 1 2 Hardy, GH ; Littlewood, JE (1916). "การมีส่วนร่วมในทฤษฎีของฟังก์ชันซีตาของรีมันน์และทฤษฎีการกระจายของจำนวนเฉพาะ" Acta Mathematica . 41 : 119– 196. doi : 10.1007/BF02422942 .
  16. ↑ ลันเดา อี. (1924). "Über ตาย Anzahl der Gitterpunkte ใน gewissen Bereichen. IV" [เกี่ยวกับจำนวนจุดกริดในภูมิภาคที่ทราบ] . นัชร. เกเซลล์. วิส. เก็ทท์. คณิตศาสตร์-phys (ภาษาเยอรมัน): 137– 150. 
  17. ↑บัลกาซาร์, โฮเซ่ แอล.; กาบาร์โร, โจอาควิม. "คลาสความซับซ้อนไม่สม่ำเสมอที่ระบุโดยขอบเขตล่างและบน" (PDF ) RAIRO - สารสนเทศเชิงทฤษฎีและการประยุกต์ - Informatique Théorique และการประยุกต์ใช้งาน23 (2): 180. ISSN 0988-3754 . เก็บถาวร(PDF)จากต้นฉบับเมื่อวันที่ 14 มีนาคม 2017 . สืบค้นเมื่อ 14 มีนาคม 2017 –จาก Numdam. 
  18. ↑ Cucker, Felipe; Bürgisser, Peter (2013). "A.1 Big Oh, Little Oh, and Other Comparisons" . Condition: The Geometry of Numerical Algorithms . Berlin, Heidelberg: Springer. หน้า467– 468. doi : 10.1007/978-3-642-38896-5 . ISBN  978-3-642-38896-5.
  19. ↑ตัวอย่างเช่น มีการละเว้นใน: Hildebrand, AJ "Asymptotic Notations" (PDF)ภาควิชาคณิตศาสตร์วิธีการเชิงอะซิมโทติกในการวิเคราะห์ Math 595 ภาคเรียนฤดูใบไม้ร่วง 2009 Urbana, IL: มหาวิทยาลัยอิลลินอยส์เก็บถาวร(PDF)จากต้นฉบับเมื่อวันที่ 14 มีนาคม 2017 เรียกดูเมื่อวันที่ 14 มีนาคม 2017 
  20. ↑คอร์เมน และคณะ 2022 , หน้า. 57.
  21. ↑คอร์เมน และคณะ 2022 , หน้า. 74–75.
  22. ↑ Andreas Björklund และ Thore Husfeldt และ Mikko Koivisto (2009). "การแบ่งเซตผ่านการรวมและการแยกออก" (PDF) . SIAM Journal on Computing . 39 (2): 546– 563. doi : 10.1137/070683933 . เก็บถาวร(PDF)จากต้นฉบับเมื่อ 2022-02-03 . เรียกดูเมื่อ2022-02-03 .ดูหัวข้อ 2.3 หน้า 551
  23. ↑ Erdelyi, A. (1956). การขยายเชิงอะซิมโทติก . บริษัท คูเรียร์. ISBN 978-0-486-60318-6.{{cite book}}: ISBN / วันที่ไม่ตรงกัน (ขอความช่วยเหลือ )
  24. ↑ Hardy, GH (1966–1979). รวมบทความของ GH Hardy (รวมถึงบทความร่วมกับ JE Littlewood และคนอื่นๆ) 7 เล่ม . สำนักพิมพ์ Clarendon Press, อ็อกซ์ฟอร์ด.
  25. ↑ Hardy, GH; Wright, EM (2008) [ฉบับพิมพ์ครั้งที่ 1 ปี 1938]. "1.6. สัญลักษณ์บางอย่าง". บทนำสู่ทฤษฎีจำนวนปรับปรุงโดยDR Heath-BrownและJH Silvermanพร้อมคำนำโดยAndrew Wiles ( ฉบับพิมพ์ครั้งที่ 6). อ็อกซ์ฟอร์ด: สำนักพิมพ์มหาวิทยาลัยอ็อกซ์ฟอร์ด. ISBN  978-0-19-921985-8.
  26. 1 2 เดอ บรุยน์, NG (1958) วิธีเชิงเส้นกำกับในการวิเคราะห์ อัมสเตอร์ดัม: ฮอลแลนด์เหนือ หน้า5– 7. ISBN  978-0-486-64221-5เก็บถาวรจากต้นฉบับเมื่อ 2023-01-17 เรียกดูเมื่อ2021-09-15{{cite book}}: ความไม่เข้ากันของหมายเลข ISBN / วันที่ ( ขอความช่วยเหลือ )
  27. 1 2 3 Graham, Ronald ; Knuth, Donald ; Patashnik, Oren (1994). คณิตศาสตร์รูปธรรม ( ฉบับที่ 2). เรดดิง, แมสซาชูเซตส์: Addison–Wesley. หน้า446. ISBN   978-0-201-55802-9เก็บถาวรจากต้นฉบับเมื่อ 2023-01-17 เรียกดูเมื่อ2016-09-23
  28. ↑ Donald Knuth (มิถุนายน–กรกฎาคม 1998). "สอนแคลคูลัสด้วย Big O" (PDF) . ประกาศของสมาคมคณิตศาสตร์อเมริกัน . 45 (6): 687. เก็บถาวร(PDF)จากต้นฉบับเมื่อ 2021-10-14 . สืบค้นเมื่อ2021-09-05 .( ฉบับเต็มเก็บ ถาวรเมื่อ วันที่ 13 พฤษภาคม 2008 ที่Wayback Machine )
  29. ↑ Donald E. Knuth, ศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ เล่ม 1 อัลกอริทึมพื้นฐาน ฉบับที่สาม Addison Wesley Longman, 1997 ส่วนที่ 1.2.11.1
  30. ↑ Ronald L. Graham, Donald E. Knuth และ Oren Patashnik,คณิตศาสตร์รูปธรรม: รากฐานสำหรับวิทยาศาสตร์คอมพิวเตอร์ (ฉบับที่ 2) , Addison-Wesley, 1994. ส่วนที่ 9.2, หน้า 443.
  31. ↑ศิวรัม อัมพกะศรัน และ เอริก ดาร์ฟ, อันโอ(เอ็นบันทึก⁡เอ็น){\displaystyle {\mathcal {O}}(N\log N)}ตัวแก้ปัญหาโดยตรงที่รวดเร็วสำหรับเมทริกซ์กึ่งแยกส่วนลำดับชั้นบางส่วน, J. Scientific Computing 57 (2013), ฉบับที่ 3, 477–501
  32. ↑ Saket Saurabh และ Meirav Zehavi,(เค,n−เค){\displaystyle (k,n-k)}-Max-Cut: Anโอ*(2พี){\displaystyle {\mathcal {O}}^{*}(2^{p})}-อัลกอริทึมเวลาและเคอร์เนลพหุนาม, Algorithmica 80 (2018), ฉบับที่ 12, 3844–3860

หมายเหตุ

  1. ↑โปรดทราบว่า "ขนาด" ของข้อมูลป้อนเข้าโดยทั่วไปจะใช้เป็นตัวบ่งชี้ว่าปัญหาในแต่ละกรณีมีความท้าทายมากน้อยเพียงใด ปริมาณเวลา [การประมวลผล] และปริมาณพื้นที่ [หน่วยความจำ] ที่จำเป็นในการคำนวณคำตอบ (หรือเพื่อ "แก้ปัญหา" นั้น) ถือเป็นตัวบ่งชี้ความยากของปัญหาในแต่ละกรณีสำหรับวัตถุประสงค์ของทฤษฎีความซับซ้อนของการคำนวณ Bigโอ{\displaystyle O}สัญลักษณ์นี้ใช้สำหรับกำหนดขอบเขตบนของ [ลำดับขนาดของ] ทั้ง 3 อย่าง ได้แก่ ขนาดของ [กระแสข้อมูล] ขาเข้า ปริมาณ [เวลา] ที่ต้องการ [ในการประมวลผล] และปริมาณ [พื้นที่หน่วยความจำ] ที่ต้องการ
  2. ↑ชื่อนี้ปรากฏอยู่ในชื่อบทความของ Knuth ในปี 1976 และไม่ปรากฏที่อื่นใดในบทความนั้นอีกเลย แทบจะไม่เคยหรืออาจไม่เคยใช้เลยด้วยซ้ำ

อ่านเพิ่มเติม

  • Knuth, Donald (1997). "1.2.11: การนำเสนอเชิงอะซิมโทติก" อัลกอริทึมพื้นฐานศิลปะแห่งการเขียนโปรแกรมคอมพิวเตอร์ เล่ม 1 (  ฉบับที่ 3). Addison-Wesley. ISBN 978-0-201-89683-1.
  • Sipser, Michael (1997). บทนำสู่ทฤษฎีการคำนวณ . สำนักพิมพ์ PWS. หน้า226–228 . ISBN  978-0-534-94728-6.
  • Avigad, Jeremy; Donnelly, Kevin (2004). การกำหนดรูปแบบสัญลักษณ์ O ใน Isabelle/HOL อย่างเป็นทางการ (PDF)การประชุมนานาชาติร่วมว่าด้วยการให้เหตุผลอัตโนมัติdoi : 10.1007/978-3-540-25984-8_27 .
  • แบล็ก, พอล อี. (11 มีนาคม 2548). แบล็ก, พอล อี. (บรรณาธิการ). "สัญกรณ์บิ๊กโอ" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล . สถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐอเมริกา. สืบค้นเมื่อ16 ธันวาคม 2549 .
  • แบล็ก, พอล อี. (17 ธันวาคม 2004). แบล็ก, พอล อี. (บรรณาธิการ). "สัญกรณ์ลิตเติล-โอ"พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูลสถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐอเมริกาสืบค้นเมื่อ16 ธันวาคม 2006
  • แบล็ก, พอล อี. (17 ธันวาคม 2004). แบล็ก, พอล อี. (บรรณาธิการ). "Ω" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล . สถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐอเมริกา. สืบค้นเมื่อ16 ธันวาคม 2006 .
  • แบล็ก, พอล อี. (17 ธันวาคม 2004). แบล็ก, พอล อี. (บรรณาธิการ). "ω" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล . สถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐอเมริกา. สืบค้นเมื่อ16 ธันวาคม 2006 .
  • แบล็ก, พอล อี. (17 ธันวาคม 2004). แบล็ก, พอล อี. (บรรณาธิการ). "Θ" . พจนานุกรมอัลกอริทึมและโครงสร้างข้อมูล . สถาบันมาตรฐานและเทคโนโลยีแห่งชาติสหรัฐอเมริกา. สืบค้นเมื่อ16 ธันวาคม 2006 .
ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Big_O_notation&oldid=1361522390#Little-o_notation "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ สัญกรณ์บิ๊กโอ

สัญกรณ์Big Oเป็นสัญกรณ์ทางคณิตศาสตร์ที่อธิบายขนาดโดยประมาณของฟังก์ชันบนโดเมน Big O เป็นสมาชิกของกลุ่มสัญกรณ์ที่คิดค้นโดยนักคณิตศาสตร์ชาวเยอรมันPaul Bachmann และEdmund Landau...

คำจำกัดความอย่างเป็นทางการ

อนุญาต เอฟ , {\textstyle f,} ฟังก์ชันที่จะประมาณค่า อาจเป็น ฟังก์ชันค่า จริง หรือ ค่า เชิงซ้อน ที่กำหนดบน โดเมน ดี , {\textstyle D,} และปล่อยให้ จี , {\textstyle g,} ฟังก์ชันเปรียบเทียบ ต้องเป็นฟังก์ชันค่าจริงที่ไม่เป็นลบ ซึ่งกำหนดบนเซตเดียวกัน ดี .

เวอร์ชั่นเซ็ตของบิ๊กโอ

ในวิทยาการคอมพิวเตอร์ [ 3 ] เป็นเรื่องปกติที่จะกำหนด O "}},"i":0}}]}">ขนาดใหญ่ โอ {\textstyle O} รวมถึงการกำหนด ชุด ฟังก์ชันด้วย โดยใช้ฟังก์ชันที่เป็นบวก (หรือไม่เป็นลบ) จี ( x ) {\displaystyle g(x)} ตามที่ระบุไว้ การตีความหนึ่ง โอ ( จี ( x ) ) {\textstyle...

ตัวอย่างที่มีโดเมนอนันต์

ในการใช้งานทั่วไป โอ {\displaystyle O} สัญลักษณ์นี้ใช้กับช่วงอนันต์ของจำนวนจริง [ เอ , ∞ ) {\displaystyle [a,\infty )} และจับภาพพฤติกรรมของฟังก์ชันสำหรับค่าขนาดใหญ่มาก x {\displaystyle x} ในบริบทนี้ การมีส่วนร่วมของคำศัพท์ที่เติบโต "เร็วที่สุด"...