تدوين كبير​

📅 آخر تحديث: ٣٠ يوليو ٢٠٢٦
✍️ نُشر في: ٣٠ يوليو ٢٠٢٦
📷 يحتوي على 347 صور
الموسوعة الحرة

ترميز Big O هو ترميز رياضي يصف الحجم التقريبي لدالة على مجال معين . يُعد Big O أحد رموز عائلة ابتكرها عالما الرياضيات الألمانيان بول باخمان [ 1 ] وإدموند لانداو [ 2 ] ، ثم قام آخرون بتطويرها، وتُعرف مجتمعةً باسم ترميز باخمان-لانداو . يرمز الحرف O إلى Ordnung ، أي رتبة التقريب .

في علوم الحاسوب ، يُستخدم ترميز Big O لتصنيف الخوارزميات بناءً على كيفية تزايد وقت تشغيلها أو متطلبات مساحتها مع زيادة المُدخلات. [ 3 ] في نظرية الأعداد التحليلية ، يُعبّر ترميز Big O عن حدود نمو دالة حسابية ، كما هو الحال بالنسبة لحد الباقي في نظرية الأعداد الأولية . [ 4 ] في التحليل الرياضي ، بما في ذلك حساب التفاضل والتكامل ، يُحدّد ترميز Big O الخطأ عند اقتطاع متسلسلة قوى ، ويُعبّر عن جودة تقريب دالة حقيقية أو مركبة بدالة أبسط.

غالبًا ما يُستخدم رمز O الكبير لوصف الدوال وفقًا لمعدلات نموها عندما يكبر المتغير: إذ يمكن تمثيل دوال مختلفة لها نفس معدل النمو التقاربي باستخدام نفس رمز O. يُستخدم الحرف O لأن معدل نمو الدالة يُشار إليه أيضًا برتبة الدالة . ولا يُقدم وصف الدالة باستخدام رمز O الكبير سوى حد أعلى لمعدل نموها.

يرتبط برمز Big O العديد من الرموز ذات الصلة، والتي تستخدم الرموزo{\displaystyle o}،∼{\displaystyle \sim }،Ωأوميغا،≪{\displaystyle \ll }،≫{\displaystyle \gg }،≍{\displaystyle \asymp }،ω{\displaystyle \omega }، وΘ{\displaystyle \Theta }لوصف أنواع أخرى من الحدود المفروضة على معدلات النمو. [ 5 ] [ 6 ] [ 7 ] [ 8 ]

اقترح باخمان هذا الترميز في عام 1894 وقام لاندو بتوسيعه في عام 1909. وقد اقترح بول دو بوا ريموند ترميزًا سابقًا في عام 1870. [ 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)  وoر ألل  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}يُطلق عليه اسم الثابت الضمني لأنه عادةً لا يتم تحديده. عند استخدام bigيا{\textstyle O}فيما يتعلق بالترميز، فإن المهم هو أن يكون هناك عدد محدودم{\displaystyle M}إن وجودها، وليس قيمتها المحددة، يُبسط عرض العديد من المتباينات التحليلية.

بالنسبة للدوال المعرفة على الأعداد الحقيقية الموجبة أو الأعداد الصحيحة الموجبة، لا يزال تعريف أكثر تقييدًا ومثيرًا للجدل نوعًا ما شائع الاستخدام، [ 3 ] [ 10 ] وخاصة في علوم الحاسوب. عند حصرها على الدوال التي تكون موجبة في النهاية ، فإن الترميز

و(x)=يا(ز(x)) أsx→∞{\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.}

في ثلاثينيات القرن العشرين، [ 6 ] قدم عالم نظرية الأعداد الروسي آي إم فينوغرادوف الترميز≪،{\displaystyle \ll ,}والتي ازداد استخدامها في نظرية الأعداد [ 4 ] [ 11 ] [ 12 ] وفروع أخرى من الرياضيات، كبديل لـيا{\textstyle O}الترميز. لدينا

 و≪ز⟺و=يا(ز).{\displaystyle \ f\ll g\iff f=O{\bigl (}g{\bigr )}.}

غالباً ما يتم استخدام كلا الرمزين في نفس العمل.

نسخة المجموعة من Big O

في علوم الحاسوب [ 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}}أن يكون بلا حدود.

عندما تكون الدالةتي(ن){\displaystyle T(n)}يصف عدد الخطوات المطلوبة في خوارزمية ذات مدخلاتن{\displaystyle n}تعبير مثل تي(ن)=يا(ن2){\displaystyle T(n)=O(n^{2})} مع كون المجال الضمني هو مجموعة الأعداد الصحيحة الموجبة، يمكن تفسير ذلك على أنه يعني أن الخوارزمية لها على الأكثر رتبةن2{\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،ت∈R.{\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}عدد صحيح موجب ن{\displaystyle n}يمكن كتابة الدالة كمجموع محدود لدوال أخرى، وعندئذٍ تحدد الدالة الأسرع نموًا رتبة الدالة.و(ن){\displaystyle f(n)}. على سبيل المثال،

و(ن)=9سجل⁡ن+5(سجل⁡ن)4+3ن2+2ن3=يا(ن3)ل ن≥1.{\displaystyle f(n)=9\log n+5(\log n)^{4}+3n^{2}+2n^{3}=O(n^{3})\qquad {\text{for }}n\geq 1.}

بعض القواعد العامة حول النمو نحو اللانهاية ؛ يمكن إثبات الخاصيتين الثانية والثالثة أدناه بدقة باستخدام قاعدة لوبيتال :

تهيمن القوى الكبرى على القوى الصغرى

لب≥أ{\displaystyle b\geq a}، ثم نأ=يا(نب){\displaystyle n^{a}=O(n^{b})} مثلن→∞{\displaystyle n\to \infty }.

تهيمن القوى على اللوغاريتمات

لأي شيء إيجابيأ،ب،{\displaystyle a,b,}(سجل⁡ن)أ=ياأ،ب(نب)،{\displaystyle (\log n)^{a}=O_{a,b}(n^{b}),} بغض النظر عن حجمهاأ{\displaystyle a}وهو صغير الحجم ب{\displaystyle b}هنا، يعتمد الثابت الضمني على كليهماأ{\displaystyle a}وب{\displaystyle b}.

تهيمن القوى الأسية

لأي شيء إيجابيأ،ب،{\displaystyle a,b,}نأ=ياأ،ب(هـبن)،{\displaystyle n^{a}=O_{a,b}(e^{bn}),} بغض النظر عن حجمهاأ{\displaystyle a}وهو صغير الحجم ب{\displaystyle b}يكون.

دالة تنمو أسرع مننج{\displaystyle n^{c}}لأيج{\displaystyle c}يُطلق عليها اسم متعددة الحدود الفائقة . وهي دالة تنمو ببطء أكثر من أي دالة أسية من الشكلجن{\displaystyle c^{n}}معج>1{\displaystyle c>1}يُطلق عليه اسم شبه أسي . قد تتطلب الخوارزمية وقتًا يكون فائقًا متعدد الحدود وشبه أسي في آن واحد؛ ومن أمثلة ذلك أسرع الخوارزميات المعروفة لتحليل الأعداد الصحيحة إلى عواملها الأولية والدالةنسجل⁡ن{\displaystyle n^{\log n}}.

يجوز لنا تجاهل أي صلاحيات لـن{\displaystyle n}داخل اللوغاريتمات. لأي عدد موجبج{\displaystyle c}، التدوينيا(سجل⁡ن){\displaystyle O(\log n)}يعني نفس الشيء تمامًايا(سجل⁡(نج)){\displaystyle O(\log(n^{c}))}، منذسجل⁡(نج)=جسجل⁡ن{\displaystyle \log(n^{c})=c\log n}وبالمثل، فإن اللوغاريتمات ذات الأساسات الثابتة المختلفة متكافئة فيما يتعلق بترميز Big O. من ناحية أخرى، فإن الدوال الأسية ذات الأساسات المختلفة ليست من نفس الرتبة. على سبيل المثال،2ن{\displaystyle 2^{n}}و3ن{\displaystyle 3^{n}}ليست من نفس الرتبة.

تعابير أكثر تعقيداً

في الاستخدامات الأكثر تعقيدًا،يا(⋅){\displaystyle O(\cdot )}يمكن أن تظهر في أماكن مختلفة في المعادلة، حتى عدة مرات على كل جانب. على سبيل المثال، ما يلي صحيح بالنسبة لـن{\displaystyle n}عدد صحيح موجب: (ن+1)2=ن2+يا(ن)،(ن+يا(ن1/2))⋅(ن+يا(سجل⁡ن))2=ن3+يا(ن5/2)،نيا(1)=يا(هـن).{\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 )}على الجانب الأيمن، بحيث يؤدي استبدال جميع هذه الدوال في المعادلة إلى تساوي الطرفين. على سبيل المثال، تعني المعادلة الثالثة أعلاه: "لأي دالة تحققو(ن)=يا(1){\displaystyle f(n)=O(1)}هناك وظيفة ماز(ن)=يا(هـن){\displaystyle g(n)=O(e^{n})}بحيثنو(ن)=ز(ن){\displaystyle n^{f(n)}=g(n)}الثابت الضمني في العبارةز(ن)=يا(هـن){\displaystyle g(n)=O(e^{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}}}

≫ لفينوغرادوف و Ω الكبيرة لكنوت

متىو،ز{\displaystyle f,g}كلاهما دالتان موجبتان، وقد قدم فينوغرادوف [ 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).}

في عام 1976، عرّف دونالد كنوث [ 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)}.

لكن في وقت سابق بكثير، قام هاردي وليتلوود [ 7 ] بتعريفΩ{\displaystyle \Omega }بشكل مختلف ، ويحظى ترميزهم بانتشار واسع اليوم في نظرية الأعداد التحليلية. [ 13 ] [ 11 ] [ 12 ] مبرراً استخدامه لـΩ{\displaystyle \Omega }[ 8 ] كتب كنوت: "بالنسبة لجميع التطبيقات التي رأيتها حتى الآن في علوم الحاسوب، فإن شرطًا أقوى... هو الأنسب بكثير". وكتب كنوت أيضًا: "على الرغم من أنني غيرت تعريف هاردي وليتلوود لـΩ{\displaystyle \Omega }أشعر أنني مُحِقٌّ في القيام بذلك لأن تعريفهم ليس شائع الاستخدام بأي حال من الأحوال، ولأن هناك طرقًا أخرى للتعبير عما يريدون قوله في الحالات النادرة نسبيًا التي ينطبق فيها تعريفهم. [ 8 ] كتاب كنوت الكبيرΩ{\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))}يعود أصل هذا الترميز إلى هاردي. [ 5 ] أما ترميز كنوت لنفس المفهوم فهوو(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}عندما تُعرَّف الدوال على الأعداد الصحيحة الموجبة أو الأعداد الحقيقية الموجبة، كما هو الحال مع Big O، غالبًا ما يُفسِّر الكُتّاب العبارات و(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 }بالنسبة للبيان. على سبيل المثال، 2ن2-10ن=Θ(ن2){\displaystyle 2n^{2}-10n=\Theta (n^{2})} ينطبق هذا على المجالن≥6{\displaystyle n\geq 6}لكنها خاطئة إذا كان المجال هو جميع الأعداد الصحيحة الموجبة، لأن الدالة تساوي صفرًا عندن=5{\displaystyle n=5}.

أمثلة أخرى

ن3+20ن2+ن+12≍ن3 للجميع ن≥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.}

الترميز

و(ن)=هـΩ(ن) للجميع ن≥1،{\displaystyle f(n)=e^{\Omega (n)}\quad {\text{ for all }}n\geq 1,} هذا يعني وجود ثابت موجبم{\displaystyle M} لهذا السبب.و(ن)≥هـمن{\displaystyle f(n)\geq e^{Mn}}للجميعن≥1{\displaystyle n\geq 1}على النقيض من ذلك، و(ن)=هـ-يا(ن) للجميع ن≥1،{\displaystyle f(n)=e^{-O(n)}\quad {\text{ for all }}n\geq 1,} هذا يعني وجود ثابت موجبم{\displaystyle M} لهذا السبب.و(ن)≥هـ-من{\displaystyle f(n)\geq e^{-Mn}}للجميعن≥1{\displaystyle n\geq 1}و و(ن)=هـΘ(ن) للجميع ن≥1،{\displaystyle f(n)=e^{\Theta (n)}\quad {\text{ for all }}n\geq 1,} هذا يعني وجود ثوابت موجبةم،شمال{\displaystyle M,N} لهذا السبب.هـمن≤و(ن)≤هـشمالن{\displaystyle e^{Mn}\leq f(n)\leq e^{Nn}}للجميعن≥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)ن{\displaystyle (-1)^{n}}باستخدام جدول بحث ذي حجم ثابت
يا(α(ن)){\displaystyle O(\alpha (n))}دالة أكرمان العكسيةالتعقيد المستهلك لكل عملية لهيكل بيانات المجموعة المنفصلة
يا(سجل⁡سجل⁡ن){\displaystyle O(\log \log n)}اللوغاريتم المزدوجمتوسط ​​عدد المقارنات التي تم إجراؤها للعثور على عنصر باستخدام البحث بالاستيفاء في مصفوفة مرتبة من القيم الموزعة بشكل منتظم
يا(سجل⁡ن){\displaystyle O(\log n)}اللوغاريتميإيجاد عنصر في مصفوفة مرتبة باستخدام البحث الثنائي أو شجرة البحث المتوازنة، بالإضافة إلى جميع العمليات في كومة ذات الحدين
يا((سجل⁡ن)ج){\displaystyle O((\log n)^{c})}ج>1{\textstyle c>1}متعدد اللوغاريتماتيمكن حل مسألة ترتيب سلسلة المصفوفات في وقت متعدد اللوغاريتمات على آلة وصول عشوائي متوازية .
يا(نج){\displaystyle O(n^{c})}0<ج<1{\textstyle 0<c<1}القوة الكسريةالبحث في شجرة kd، قسمة تجريبية، اختبار أولية ساذج (يا(ن){\displaystyle O({\sqrt {n}})})
يا(ن){\displaystyle O(n)}خطيإيجاد عنصر في قائمة غير مرتبة أو في مصفوفة غير مرتبة؛ جمع عددين صحيحين من n بت عن طريق الحمل المتتالي
يا(نسجل*⁡ن){\displaystyle O(n\log ^{*}n)}ن لوغاريتم النجمة نإجراء عملية التثليث لمضلع بسيط باستخدام خوارزمية سايدل، [ 14 ] حيثسجل*⁡(ن)={0،لو ن≤11+سجل*⁡(سجل⁡ن)،لو ن>1{\displaystyle \log ^{*}(n)={\begin{cases}0,&{\text{if }}n\leq 1\\1+\log ^{*}(\log n),&{\text{if }}n>1\end{cases}}}
يا(نسجل⁡ن)=يا(سجل⁡ن!){\displaystyle O(n\log n)=O(\log n!)}خطي لوغاريتمي ، لوغاريتمي خطي، شبه خطي، أو "نسجل⁡ن{\displaystyle n\log n}"إجراء تحويل فورييه السريع ؛ فرز المقارنة بأسرع ما يمكن ؛ فرز الكومة وفرز الدمج
يا(ن2){\displaystyle O(n^{2})}التربيعيضرب اثنينن{\displaystyle n}أعداد مكونة من خانة واحدة باستخدام الضرب في الكتب المدرسية ؛ خوارزميات فرز بسيطة، مثل فرز الفقاعات ، وفرز التحديد ، وفرز الإدراج ؛ الحد الأقصى (في أسوأ الحالات) لبعض خوارزميات الفرز الأسرع عادةً، مثل الفرز السريع ، وفرز شيل ، وفرز الشجرة.
يا(نج){\displaystyle O(n^{c})}متعدد الحدود أو جبريتحليل قواعد النحو المتجاورة الشجرية ؛ المطابقة القصوى للرسوم البيانية ثنائية الأجزاء ؛ إيجاد المحدد باستخدام تحليل LU
لن[α،ج]=هـ(ج+o(1))(ln⁡ن)α(ln⁡ln⁡ن)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 أو شبه الأسيتحليل عدد باستخدام المنخل التربيعي أو منخل حقل الأعداد
يا(جن){\displaystyle O(c^{n})}ج>1{\textstyle c>1}النمو الأسيإيجاد الحل (الدقيق) لمسألة البائع المتجول باستخدام البرمجة الديناميكية ؛ تحديد ما إذا كانت عبارتان منطقيتان متكافئتين باستخدام البحث الشامل
يا(ن!){\displaystyle O(n!)}العامليحل مسألة البائع المتجول باستخدام البحث الشامل؛ توليد جميع التباديل غير المقيدة لمجموعة مرتبة جزئيًا ؛ إيجاد المحدد باستخدام توسيع لابلاس ؛ تعداد جميع تجزئات مجموعة

البيانو(ن)=يا(ن!){\displaystyle f(n)=O(n!)}يُضعف أحيانًا إلىو(ن)=يا(نن){\displaystyle f(n)=O\left(n^{n}\right)}لاستخلاص صيغ أبسط للتعقيد التقاربي. في العديد من هذه الأمثلة، يكون وقت التشغيل في الواقعΘ(ز(ن)){\displaystyle \Theta (g(n))}مما ينقل مزيداً من الدقة.

تدوين الحرف الصغير o

بالنسبة للدوال الحقيقية أو المركبة ذات المتغير الحقيقي x{\displaystyle x}معز(x)>0{\displaystyle g(x)>0}لكبير بما فيه الكفايةx{\displaystyle x}يكتب أحدهم [ 2 ]

و(x)=o(ز(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=o(x2){\displaystyle 200x=o(x^{2})}و1/x=o(1)،{\displaystyle 1/x=o(1),}  كلاهماx→∞.{\displaystyle x\to \infty .}

عندما يهتم المرء بسلوك دالة ما لقيم كبيرة منx{\displaystyle x}تُقدّم صيغة little-o بيانًا أقوى من صيغة big-O المقابلة: كل دالة من نوع little-oز{\displaystyle g}هو أيضًا Big-O منز{\displaystyle g}على فترة زمنية معينة[أ،∞){\displaystyle [a,\infty )}لكن ليس كل دالة من نوع Big-Oز{\displaystyle g}هو حرف o الصغير منز{\displaystyle g}. على سبيل المثال،2x2=يا(x2){\displaystyle 2x^{2}=O(x^{2})}لكن2x2≠o(x2){\displaystyle 2x^{2}\neq o(x^{2})}لx≥1{\displaystyle x\geq 1}.

يحترم الحرف الصغير "o" عددًا من العمليات الحسابية. على سبيل المثال،

لوج{\displaystyle c}ثابت غير صفري وو=o(ز){\displaystyle f=o(g)}ثمج⋅و=o(ز){\displaystyle c\cdot f=o(g)}، و
لوو=o(F){\displaystyle f=o(F)}وز=o(جي){\displaystyle g=o(G)}ثمو⋅ز=o(F⋅جي).{\displaystyle f\cdot g=o(F\cdot G).}
لوو=o(F){\displaystyle f=o(F)}وز=o(جي){\displaystyle g=o(G)}ثمو+ز=o(F+جي){\displaystyle f+g=o(F+G)}

كما أنها تحقق علاقة التعدي :

لوو=o(ز){\displaystyle f=o(g)}وز=o(ح){\displaystyle g=o(h)}ثمو=o(ح).{\displaystyle f=o(h).}

يمكن أيضًا تعميم Little-o على الحالة المحدودة: [ 2 ]و(x)=o(ز(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+o(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+o(x2)x=ليمx→01+o(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}

الترميز التقاربي

العلاقة المتعلقة بالحرف الصغير 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.} يمكن ربط هذا بـ "الحرف الصغير" من خلال ملاحظة أن و(x)∼ز(x){\displaystyle f(x)\sim g(x)}وهو ما يعادل أيضًا و(x)=(1+o(1))ز(x){\displaystyle f(x)=(1+o(1))g(x)}. هناo(1){\displaystyle o(1)}يشير إلى دالة تقترب من الصفر كـx→∞{\displaystyle x\to \infty }يقرأ المرء هذا على النحو التالي:و(x){\displaystyle f(x)}هو مقارب لـز(x){\displaystyle g(x)}بالنسبة للدوال غير الصفرية على نفس المجال (المحدود أو غير المحدود)،∼{\displaystyle \sim }يشكل علاقة تكافؤ .

إحدى أشهر النظريات التي تستخدم الترميز ∼{\displaystyle \sim }هي صيغة ستيرلينغن!∼(نهـ)ن2πن مثل ن→∞.{\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}.

كما هو الحال مع العدد الصغير o، توجد نسخة ذات حدود محدودة (ذات جانبين أو ذات جانب واحد ) أيضًا، على سبيل المثال الخطيئة⁡x∼x مثل x→0.{\displaystyle \sin x\sim x\quad {\text{ as }}x\to 0.}

أمثلة أخرى: xأ=oأ،ب(هـب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)+o(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 ).}∑ن=1∞1نs∼1s-1(s→1+).{\displaystyle \sum _{n=1}^{\infty }{\frac {1}{n^{s}}}\sim {\frac {1}{s-1}}\quad (s\to 1^{+}).} الخاصية التقاربية الأخيرة هي خاصية أساسية لدالة زيتا لريمان .

𝜔 الصغير لكنوت

بالنسبة للدوال الحقيقية ذات القيم الموجبة في النهايةو،ز،{\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)=o(و(x)){\displaystyle g(x)=o(f(x))}بمعنى آخر، هذا يعني أنو(x){\displaystyle f(x)} ينمو أسرع بكثير منز(x){\displaystyle g(x)}.

تدوين هاردي-ليتلوود Ω

في عام 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)=o(ز(x)) .{\displaystyle ~f(x)=o(g(x))~.}

وفي عام 1916، قدم المؤلفون أنفسهم الرمزين الجديدين. ΩR {\displaystyle \ \Omega _{R}\ }و Ωل ،{\displaystyle \ \Omega _{L}\ ,}تم تعريفها على النحو التالي: [ 15 ]

و(x)=ΩR(ز(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~.}

استخدم إي. لانداو هذه الرموز ، بنفس المعاني، في عام 1924. [ 16 ] ومع ذلك، يستخدم المؤلفون الذين تبعوا لانداو تدوينًا مختلفًا لنفس التعريفات: [ 11 ] الرمز ΩR {\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 ~.}

عائلة رموز باخمان-لانداو

لفهم التعريفات الرسمية، راجع قائمة الرموز المنطقية المستخدمة في الرياضيات.

الترميزالاسم [ 8 ]وصفالتعريف الرسميتعريف الشركة

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

و(ن)=يا(ز(ن)){\displaystyle f(n)=O(g(n))}أو

و(ن)≪ز(ن){\displaystyle f(n)\ll g(n)}(تدوين فينوغرادوف)

أو الكبيرة؛ أوه الكبيرة؛ أوميكرون الكبير [ 8 ] [ ب ]|و|{\displaystyle |f|}محدودة من الأعلى بواسطة g (حتى عامل ثابت)ك{\displaystyle k})∃ك>0∀ن∈د:|و(ن)|≤كز(ن){\displaystyle \exists k>0\,\forall n\in D\colon |f(n)|\leq k\,g(n)}رشفةن∈د|و(ن)|ز(ن)<∞{\displaystyle \sup _{n\in D}{\frac {\left|f(n)\right|}{g(n)}}<\infty }
و(ن)=o(ز(ن)){\displaystyle f(n)=o(g(n))}أو صغيرة؛ أو صغيرة؛ أو صغيرة؛ أو صغيرةتهيمن الدالة g على الدالة f تقاربياً (لأي عامل ثابت)ك{\displaystyle k})∀ك>0∃ن0∀ن>ن0:|و(ن)|≤كز(ن){\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon |f(n)|\leq k\,g(n)}ليمن→∞و(ن)ز(ن)=0{\displaystyle \lim _{n\to \infty }{\frac {f(n)}{g(n)}}=0}
و(ن)=Ω(ز(ن)){\displaystyle f(n)=\Omega (g(n))}أوميغا الكبرى في نظرية الأعداد (هاردي-ليتلوود)|و|{\displaystyle |f|}لا يهيمن عليها g تقاربياً∃ك>0∀ن0∃ن>ن0:|و(ن)|≥كز(ن){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon |f(n)|\geq k\,g(n)}ليم سوبن→∞|و(ن)|ز(ن)>0{\displaystyle \limsup _{n\to \infty }{\frac {|f(n)|}{g(n)}}>0}
و(ن)=Ω+(ز(ن)){\displaystyle f(n)=\Omega _{+}(g(n))}أوميغا بلس (هاردي-ليتلوود)و{\displaystyle f}لا يهيمن عليها g تقاربياً∃ك>0∀ن0∃ن>ن0:و(ن)≥كز(ن){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon f(n)\geq k\,g(n)}ليم سوبن→∞و(ن)ز(ن)>0{\displaystyle \limsup _{n\to \infty }{\frac {f(n)}{g(n)}}>0}
و(ن)=Ω-(ز(ن)){\displaystyle f(n)=\Omega _{-}(g(n))}أوميغا ناقص (هاردي – ليتلوود)-و{\displaystyle -f}لا يهيمن عليها g تقاربياً∃ك>0∀ن0∃ن>ن0:-و(ن)≥كز(ن){\displaystyle \exists k>0\,\forall n_{0}\,\exists n>n_{0}\colon -f(n)\geq k\,g(n)}ليم سوبن→∞-و(ن)ز(ن)>0{\displaystyle \limsup _{n\to \infty }{\frac {-f(n)}{g(n)}}>0}
و(ن)=Ω±(ز(ن)){\displaystyle f(n)=\Omega _{\pm }(g(n))}أوميغا زائد وناقصلاو{\displaystyle f}ولا-و{\displaystyle -f}يهيمن عليها g تقاربياًو(ن)=Ω+(ز(ن)){\displaystyle f(n)=\Omega _{+}(g(n))}وو(ن)=Ω-(ز(ن)){\displaystyle f(n)=\Omega _{-}(g(n))}
و(ن)≍ز(ن){\displaystyle f(n)\asymp g(n)}(تدوين هاردي) أوو(ن)=Θ(ز(ن)){\displaystyle f(n)=\Theta (g(n))}(تدوين كنوت)من نفس رتبة (هاردي)؛ ثيتا الكبيرة (كنوث)الدالة f محدودة بالدالة g في الحالتين المذكورتين أعلاه (بمعامل ثابت).ك2{\displaystyle k_{2}}) وما دونه (مع عامل ثابت)ك1{\displaystyle k_{1}})∃ك1>0∃ك2>0∀ن∈د:{\displaystyle \exists k_{1}>0\,\exists k_{2}>0\,\forall n\in D\colon }ك1ز(ن)≤و(ن)≤ك2ز(ن){\displaystyle k_{1}\,g(n)\leq f(n)\leq k_{2}\,g(n)}و(ن)=يا(ز(ن)){\displaystyle f(n)=O(g(n))}وز(ن)=يا(و(ن)){\displaystyle g(n)=O(f(n))}
و(ن)∼ز(ن){\displaystyle f(n)\sim g(n)}مثلن→أ{\displaystyle n\to a}، أينأ{\displaystyle a}محدود،∞{\displaystyle \infty }

أو-∞{\displaystyle -\infty }

التكافؤ التقاربيf تساوي g تقاربياً∀ε>0∃ن0∀ن>ن0:|و(ن)ز(ن)-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 })ليمن→أو(ن)ز(ن)=1{\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=1}
و(ن)=Ω(ز(ن)){\displaystyle f(n)=\Omega (g(n))}(تدوين كنوت)، أو

و(ن)≫ز(ن){\displaystyle f(n)\gg g(n)}(تدوين فينوغرادوف)

أوميغا الكبرى في نظرية التعقيد (كنوث)الدالة f محدودة من الأسفل بالدالة g ، حتى عامل ثابت.∃ك>0∀ن∈د:و(ن)≥كز(ن){\displaystyle \exists k>0\,\forall n\in D\colon f(n)\geq k\,g(n)}معلوماتن∈دو(ن)ز(ن)>0{\displaystyle \inf _{n\in D}{\frac {f(n)}{g(n)}}>0}
و(ن)=ω(ز(ن)){\displaystyle f(n)=\omega (g(n))}مثلن→أ{\displaystyle n\to a}،

أينأ{\displaystyle a}يمكن أن تكون محدودة،∞{\displaystyle \infty }أو-∞{\displaystyle -\infty }

أوميغا الصغيرة؛ أوميغا الصغرىيهيمن f على g بشكل تقاربي∀ك>0∃ن0∀ن>ن0:و(ن)>كز(ن){\displaystyle \forall k>0\,\exists n_{0}\,\forall n>n_{0}\colon f(n)>k\,g(n)}(لأ=∞{\displaystyle a=\infty })ليمن→أو(ن)ز(ن)=∞{\displaystyle \lim _{n\to a}{\frac {f(n)}{g(n)}}=\infty }

تفترض تعريفات الحدز(ن)>0{\displaystyle g(n)>0}ل ن{\displaystyle n}في جوار الحد؛ عندما يكون الحد∞{\displaystyle \infty }وهذا يعني أنز(ن)>0{\displaystyle g(n)>0}لكبير بما فيه الكفايةن{\displaystyle n}.

يستخدم علم الحاسوب وعلم التوافيق مفهوم "الكبير"يا{\displaystyle O}ثيتا الكبيرةΘ{\displaystyle \Theta }، قليلo{\displaystyle o}أوميغا الصغيرةω{\displaystyle \omega }وأوميغا كنوت الكبيرةΩ{\displaystyle \Omega }الرموز. [ 3 ] غالبًا ما تستخدم نظرية الأعداد التحليلية الرموز الكبيرةيا{\displaystyle O}، صغيرo{\displaystyle o}هاردي≍{\displaystyle \asymp }هاردي - أوميغا ليتلوود الكبيرΩ{\displaystyle \Omega }(مع أو بدون الرموز السفلية +، - أو ±)، فينوغرادوف≪{\displaystyle \ll }و≫{\displaystyle \gg }الرموز و∼{\displaystyle \sim }الرموز. [ 11 ] [ 4 ] [ 12 ] أوميغا الصغيرةω{\displaystyle \omega }لا يُستخدم الترميز بكثرة في التحليل أو في نظرية الأعداد. [ 19 ]

جودة التقريبات باستخدام رموز مختلفة

بشكل غير رسمي، وخاصة في علوم الحاسوب، فإن الكبيريا{\displaystyle O}يمكن استخدام الترميز غالبًا بشكل مختلف إلى حد ما لوصف حد ضيق تقاربي عند استخدام قيمة كبيرة لـ ThetaΘ{\displaystyle \Theta }قد يكون استخدام الترميز أكثر ملاءمة من الناحية الواقعية في سياق معين. [ 20 ] على سبيل المثال، عند النظر في دالةتي(ن)=73ن3+22ن2+58{\displaystyle T(n)=73n^{3}+22n^{2}+58}، كل ما يلي مقبول بشكل عام، ولكن عادة ما يفضل بشدة الحدود الأكثر صرامة (مثل الأرقام 2 و3 و4 أدناه) على الحدود الأكثر مرونة (مثل الرقم 1 أدناه).

  1. تي(ن)=يا(ن100){\displaystyle T(n)=O(n^{100})}
  2. تي(ن)=يا(ن3){\displaystyle T(n)=O(n^{3})}
  3. تي(ن)=Θ(ن3){\displaystyle T(n)=\Theta (n^{3})}
  4. تي(ن)∼73ن3{\displaystyle T(n)\sim 73n^{3}}مثلن→∞{\displaystyle n\to \infty }.

مع أن العبارات الثلاث صحيحة، إلا أن كل عبارة تتضمن معلومات أكثر تدريجيًا. في بعض المجالات، يُستخدم رمز O الكبير (رقم 2 في القوائم أعلاه) بشكل أكثر شيوعًا من رمز ثيتا الكبير (رقم 3 في القوائم أعلاه). على سبيل المثال، إذاتي(ن){\displaystyle T(n)}يمثل وقت تشغيل خوارزمية مطورة حديثًا لحجم الإدخالن{\displaystyle n}، قد يكون مخترعو ومستخدمو الخوارزمية أكثر ميلاً إلى وضع حد أعلى للمدة التي سيستغرقها تشغيلها دون الإدلاء ببيان صريح حول الحد الأدنى أو السلوك التقاربي.

امتدادات لترميز باخمان-لانداو

هناك ترميز آخر يُستخدم أحيانًا في علوم الحاسوب وهويا~{\displaystyle {\tilde {O}}}(تُقرأ soft-O )، والتي تُخفي العوامل متعددة اللوغاريتمات. هناك تعريفان مستخدمان: يستخدم بعض المؤلفينو(ن)=يا~(ز(ن)){\displaystyle f(n)={\tilde {O}}(g(n))}كاختصار لـو(ن)=يا(ز(ن)سجلك⁡ن){\displaystyle f(n)=O(g(n)\log ^{k}n)}بالنسبة للبعضك{\displaystyle k}بينما يستخدمه آخرون كاختصار لـو(ن)=يا(ز(ن)سجلك⁡ز(ن)){\displaystyle f(n)=O(g(n)\log ^{k}g(n))} [ 21 ] عندما​ز(ن){\displaystyle g(n)}هي متعددة الحدود فين{\displaystyle n}لا يوجد فرق؛ ومع ذلك، يسمح التعريف الأخير بقول، على سبيل المثال، أنن2ن=يا~(2ن){\displaystyle n2^{n}={\tilde {O}}(2^{n})}بينما يسمح التعريف السابق بـسجلك⁡ن=يا~(1){\displaystyle \log ^{k}n={\tilde {O}}(1)}لأي ثابتك{\displaystyle k}يستخدم بعض المؤلفين الرمز O * لنفس الغرض الذي استخدموه في التعريف الأخير. [ 22 ] وهو في الأساس نسخة أقل دقة من رمز Big O ، حيث يتجاهل العوامل اللوغاريتمية في معدل نمو الدالة.سجلك⁡ن=o(نε){\displaystyle \log ^{k}n=o(n^{\varepsilon })} لأي ثابتك{\displaystyle k}وأي ε>0{\displaystyle \varepsilon >0}تُعد العوامل اللوغاريتمية أقل أهمية بكثير من قوىن{\displaystyle n}بل إنها أقل أهمية مقارنة بالدوال الأسية.

كما أن رمز L ، المعرّف على النحو التالي

لن[α،ج]=هـ(ج+o(1))(ln⁡ن)α(ln⁡ln⁡ن)1-α،{\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }},}

يُعد هذا مناسبًا للدوال التي تقع بين الدوال متعددة الحدود والدوال الأسية من حيثسجل⁡ن{\displaystyle \log n}.

إن تعميم ذلك على الدوال التي تأخذ قيمًا في أي فضاء متجهي معياري أمرٌ مباشر (باستبدال القيم المطلقة بالمعايير)، حيثو{\displaystyle f}وز{\displaystyle g}ليس بالضرورة أن تأخذ قيمها نفس الحيز. تعميم للدوالز{\displaystyle g}من الممكن أيضًا أخذ القيم في أي مجموعة طوبولوجية . "العملية الحدية"x→x0{\displaystyle x\to x_{0}}ويمكن تعميم ذلك أيضًا عن طريق إدخال قاعدة ترشيح عشوائية، أي للشبكات الموجهة.و{\displaystyle f}وز{\displaystyle g}. الo{\displaystyle o}يمكن استخدام الترميز لتعريف المشتقات وقابلية التفاضل في فضاءات عامة تمامًا، وكذلك التكافؤ (التقاربي) للدوال،

و∼ز⟺(و-ز)∈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≠o(x){\displaystyle 2x-x\neq o(x)}.

تاريخ

في عام 1870، حدد بول دو بوا ريموند [ 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 لأول مرة من قبل عالم نظرية الأعداد بول باخمان عام 1894، في المجلد الثاني من كتابه " نظرية الأعداد التحليلية " ( Analytische Zahlentheorie ). [ 1 ] تبناه عالم نظرية الأعداد إدموند لانداو ، ومن ثم استلهم منه تقديم الرمز o عام 1909؛ [ 2 ] ولذلك يُطلق عليهما الآن رموز لانداو. استُخدمت هذه الرموز في الرياضيات التطبيقية خلال خمسينيات القرن العشرين للتحليل التقاربي. [ 23 ]Ω{\displaystyle \Omega }(بمعنى "ليس صغيرًا من ") تم تقديمه في عام 1914 من قبل هاردي وليتلوود. [ 7 ] كما قدم هاردي وليتلوود في عام 1916 اليسار واليمينΩ{\displaystyle \Omega }الرموزΩR{\displaystyle \Omega _{R}}،Ωل{\displaystyle \Omega _{L}}(يشار إليه الآن بشكل شائع بـΩ+،Ω-{\displaystyle \Omega _{+},\Omega _{-}}[ 15 ] هذا​Ω{\displaystyle \Omega }وقد شاع استخدام الترميز في نظرية الأعداد منذ خمسينيات القرن العشرين. [ 13 ]

أدخل هاردي الرموز≼{\displaystyle \preccurlyeq }ودافع عن بوا-ريموند≺{\displaystyle \prec }(بالإضافة إلى الرموز الأخرى المذكورة سابقًا) في رسالته عام 1910 بعنوان "أُرَصُ اللانهاية"، [ 5 ] لكنه لم يستخدمها إلا في ثلاث أوراق بحثية (1910-1913). وفي ما يقرب من 400 ورقة بحثية وكتاب متبقٍ له، استخدم باستمرار رمزي لاندو O و o. [ 24 ] رموز هاردي≼{\displaystyle \preccurlyeq }و≍-{\displaystyle \mathbin {\,\asymp \;\;\;\;\!\!\!\!\!\!\!\!\!\!\!\!\!-} }لم تعد تُستخدم.

الرمز∼{\displaystyle \sim }على الرغم من استخدامه سابقًا بمعانٍ مختلفة، [ 9 ] فقد أُعطي تعريفه الحديث من قِبل لاندو عام 1909 [ 2 ] وهاردي عام 1910. [ 5 ] وفي الصفحة نفسها، عرّف هاردي الرمز≍{\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}(هذا يتوافق مع تدوين بوا-ريموند)و∼ز{\displaystyle f\sim g}).

في ثلاثينيات القرن العشرين، قام فينوغرادوف [ 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 ]

في سبعينيات القرن العشرين، شاع استخدام مصطلح "Big O" في علوم الحاسوب على يد دونالد كنوث ، الذي اقترح الترميز المختلف.و(x)=Θ(ز(x)){\displaystyle f(x)=\Theta (g(x))}لهارديو(x)≍ز(x){\displaystyle f(x)\asymp g(x)}واقترح تعريفًا مختلفًا لترميز أوميغا لهاردي وليتلوود. [ 8 ]

مسائل التدوين

الأسهم

في الرياضيات، تعبير مثلx→∞{\displaystyle x\to \infty }يشير إلى وجود حد . في ترميز Big-O والترميزات ذات الصلة Ω،Θ،≫،≪،≍{\displaystyle \Omega ,\Theta ,\gg ,\ll ,\asymp }، لا يوجد حد ضمني، على عكس الحرف الصغير 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 ] يصف كنوت هذه العبارات بأنها "معادلات أحادية الاتجاه"، لأنه إذا أمكن عكس الجانبين، "فسنتمكن من استنتاج أشياء سخيفة مثل ن=ن2{\displaystyle n=n^{2}}من الهوياتن=يا(ن2){\displaystyle n=O(n^{2})}ون2=يا(ن2){\displaystyle n^{2}=O(n^{2})}[ 27 ] وفي رسالة أخرى ، أشار كنوت أيضًا إلى أن [ 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 ]

التنضيد

يُكتب رمز O الكبير كحرف " O " كبير مائل ، كما في المثال التالي:يا(ن2){\displaystyle O(n^{2})}[ 29 ] [ 30 ] في TeX ، يُنتج هذا الرمز ببساطة عن طريق كتابة 'O' داخل وضع الرياضيات. على عكس رموز باخمان-لانداو ذات الأسماء اليونانية، لا يحتاج هذا الرمز إلى رمز خاص. مع ذلك، يستخدم بعض المؤلفين النسخة الخطية منه .يا{\displaystyle {\mathcal {O}}}بدلاً من ذلك. [ 31 ] [ 32 ]

يرمز الحرف O الكبير في الأصل إلى "رتبة" ("Ordnung"، باخمان 1894)، وهو حرف لاتيني. لم يُطلق عليه باخمان ولا لاندو اسم "أوميكرون". وفي وقت لاحق (1976)، اعتبره كنوت أوميكرون كبير ، [ 8 ] ربما في إشارة إلى تعريفه للرمز أوميغا . لا يُستخدم الرقم صفر .

انظر أيضاً

المراجع والملاحظات

  1. 1 2 باخمان، بول (1894). Analytische Zahlentheorie [ نظرية الأعداد التحليلية ] (باللغة الألمانية). المجلد.  2. لايبزيغ: تيوبنر.
  2. 1 2 3 4 5 لانداو، إدموند (1909). Handbuch der Lehre von der Verteilung der Primzahlen [ دليل حول نظرية توزيع الأعداد الأولية ] (باللغة الألمانية). لايبزيغ: بي جي تيوبنر؛ أعيد طبعه في مجلدين في مجلد واحد بواسطة تشيلسي، 1974، مع ملحق للدكتور بول تي بيتمان. ص 59 – 63. 
  3. 1 2 3 4 5 6 كورمن، توماس هـ .؛ ليسرسون، تشارلز إي .؛ ريفست، رونالد ل .؛ شتاين، كليفورد (2022). "توصيف أوقات التشغيل". مقدمة في الخوارزميات ( الطبعة الرابعة). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. ISBN  978-0-262-53091-0.
  4. 1 2 3 4 5 6 إيوانيك، هنريك ؛ كوالسكي، إيمانويل (2004). نظرية الأعداد التحليلية . الجمعية الرياضية الأمريكية.
  5. 1 2 3 4 5 هاردي، جي إتش (1910). مراتب اللانهاية: "حساب اللانهاية" لبول دو بوا-ريموند . مطبعة جامعة كامبريدج . ص 2. 
  6. 1 2 3 4 فينوغرادوف، ماتفييفيتش (1934). “تقدير جديد لـ G ( n ) في مشكلة وارنج”. دوكلادي أكاديمي ناوك SSSR (بالروسية). 5 ( 5 – 6): 249 – 253.
    مترجم إلى الإنجليزية في:
    فينوغرادوف، ماتفييفيتش (1985). مختارات من أعمال إيفان ماتفييفيتش فينوغرادوف؛ أعدها معهد ستيكلوف للرياضيات التابع لأكاديمية العلوم في الاتحاد السوفيتي بمناسبة عيد ميلاده التسعين . دار نشر سبرينغر.
  7. 1 2 3 4 5 هاردي، جي إتش ؛ ليتلوود، جي إي (1914). "بعض مسائل التقريب الديوفانتي: الجزء الثاني. المتسلسلة المثلثية المرتبطة بدوال θ الإهليلجية " . أكتا ماتيماتيكا . 37 : 225. doi : 10.1007/BF02401834 . مؤرشف من الأصل في 12 ديسمبر 2018. تم الاسترجاع في 14 مارس 2017 . 
  8. 1 2 3 4 5 6 7 8 9 10 كنوت، دونالد (أبريل - يونيو 1976). "أوميكرون الكبير وأوميغا الكبير وثيتا الكبير" . أخبار SIGACT . 8 (2): 18-24 . doi : 10.1145/1008328.1008329 . S2CID 5230246 . 
  9. 1 2 3 بوا ريموند، بول دو (1870). "على عظمة الوظائف اللانهائية" . أنالي دي ماتيماتيكا . السلسلة 2. 4 : 338-353 . دوى : 10.1007 / BF02420041 .
  10. ↑ سيبسر، مايكل (2012). مقدمة في نظرية الحوسبة ( الطبعة الثالثة). بوسطن، ماساتشوستس: دار نشر PWS. 
  11. 1 2 3 4 5 6 إيفيتش، أ. (1985). دالة زيتا لريمان . جون وايلي وأولاده. الفصل 9. 
  12. 1 2 3 4 5 6 7 جيرالد تيننباوم، مقدمة في نظرية الأعداد التحليلية والاحتمالية، « الرموز »، الصفحة xxiii. الجمعية الرياضية الأمريكية، بروفيدنس رود آيلاند، 2015.
  13. 1 2 إي. سي. تيتشمارش، نظرية دالة زيتا لريمان (أكسفورد؛ مطبعة كلارندون، 1951)
  14. ↑ سيدل، رايموند (1991)، "خوارزمية عشوائية تزايدية بسيطة وسريعة لحساب تجزئة شبه المنحرف وتثليث المضلعات"، الهندسة الحسابية ، 1 : 51-64 ، CiteSeerX 10.1.1.55.5877 ، doi : 10.1016/0925-7721(91)90012-4 
  15. 1 2 هاردي، جي إتش ؛ ليتلوود، جي إي (1916). "مساهمة في نظرية دالة زيتا لريمان ونظرية توزيع الأعداد الأولية". أكتا ماتيماتيكا . 41 : 119-196 . doi : 10.1007/BF02422942 .
  16. ^ لانداو، إي. (1924). "Über die Anzahl der Gitterpunkte in gewissen Bereichen. IV" [ حول عدد نقاط الشبكة في المناطق المعروفة ] . ناشر. جيزيل. ويس. جوت. الرياضيات والفيزياء. (باللغة الألمانية): 137- 150. 
  17. ^ بالكازار، خوسيه إل. غابارو، يواكيم. “فئات التعقيد غير الموحدة المحددة بالحدود الدنيا والعليا” (PDF) . رايرو – المعلوماتية النظرية والتطبيقات – المعلوماتية النظرية والتطبيقات . 23 (2): 180. ISSN 0988-3754 . أرشفة (PDF) من الأصلي في 14 مارس 2017 . تم الاسترجاع 14 مارس 2017 – عبر نومدام. 
  18. ↑ كوكر، فيليبي؛ بورغيسر، بيتر (2013). "أ.1 مقارنة بين Big O وLittle O وغيرها" . الشرط: هندسة الخوارزميات العددية . برلين، هايدلبرغ: سبرينغر. ص 467-468 . doi : 10.1007/978-3-642-38896-5 . ISBN  978-3-642-38896-5.
  19. ↑ على سبيل المثال، تم حذفه في: هيلدبراند، أ. ج. "الرموز التقاربية" (ملف PDF) . قسم الرياضيات. الأساليب التقاربية في التحليل . الرياضيات 595، خريف 2009. أوربانا، إلينوي: جامعة إلينوي. مؤرشف (ملف PDF) من الأصل في 14 مارس 2017. تم الاسترجاع في 14 مارس 2017 . 
  20. ^ كورمين وآخرون. 2022 ، ص. 57.
  21. ^ كورمين وآخرون. 2022 ، ص. 74-75.
  22. ↑ أندرياس بيوركلوند وثور هوسفيلدت وميكو كويفيستو (2009). "تقسيم المجموعات عبر الإدراج والاستبعاد" (ملف PDF) . مجلة SIAM للحوسبة . 39 (2): 546-563 . doi : 10.1137/070683933 . مؤرشف (ملف PDF) من الأصل بتاريخ 2022-02-03 . تم الاطلاع عليه بتاريخ 2022-02-03 .انظر القسم 2.3، صفحة 551.
  23. ↑ إرديلي، أ. (1956). التوسعات التقاربية . شركة كورير. ISBN 978-0-486-60318-6.{{cite book}}: عدم توافق رقم ISBN / التاريخ ( مساعدة ) .
  24. ↑ هاردي، جي إتش (1966-1979). الأوراق المجمعة لجي إتش هاردي (بما في ذلك الأوراق المشتركة مع جي إي ليتلوود وآخرين)، 7 مجلدات . مطبعة كلارندون، أكسفورد.
  25. ↑ هاردي، جي إتش؛ رايت، إي إم (2008) [الطبعة الأولى 1938]. "1.6. بعض الرموز". مدخل إلى نظرية الأعداد . مراجعة دي آر هيث-براون وجيه إتش سيلفرمان ، مع مقدمة بقلم أندرو وايلز (الطبعة السادسة ). أكسفورد: مطبعة جامعة أكسفورد. ISBN  978-0-19-921985-8.
  26. 1 2 دي بروين، إن جي (1958). الطرق المقاربة في التحليل . أمستردام: شمال هولندا. ص 5 – 7. رقم ISBN  978-0-486-64221-5أُرشف من المصدر الأصلي بتاريخ 17 يناير 2023. تم الاطلاع عليه بتاريخ 15 سبتمبر 2021 .{{cite book}}عدم توافق رقم ISBN / التاريخ ( مساعدة )
  27. 1 2 3 غراهام، رونالد ؛ كنوت، دونالد ؛ باتاشنيك، أورين (1994). الرياضيات الملموسة ( الطبعة الثانية). ريدينغ، ماساتشوستس: أديسون-ويسلي. ص 446. ISBN   978-0-201-55802-9أُرشف من المصدر الأصلي بتاريخ 17 يناير 2023. تم الاطلاع عليه بتاريخ 23 سبتمبر 2016 .
  28. ↑ دونالد كنوث (يونيو-يوليو 1998). "تدريس حساب التفاضل والتكامل باستخدام Big O" (ملف PDF) . إشعارات الجمعية الأمريكية للرياضيات . 45 (6): 687. مؤرشف (ملف PDF) من الأصل بتاريخ 14 أكتوبر 2021. تم الاطلاع عليه بتاريخ 5 سبتمبر 2021 .( النسخة الكاملة مؤرشفة بتاريخ 13 مايو 2008 على موقع Wayback Machine )
  29. ↑ دونالد إي. كنوث، فن برمجة الحاسوب. المجلد 1. الخوارزميات الأساسية، الطبعة الثالثة، أديسون ويسلي لونجمان، 1997. القسم 1.2.11.1.
  30. ↑ رونالد إل. غراهام، دونالد إي. كنوث، وأورين باتاشنيك، الرياضيات الملموسة: أساس لعلوم الحاسوب (الطبعة الثانية) ، أديسون-ويسلي، 1994. القسم 9.2، ص 443.
  31. ↑ سيفارام أمبيكاساران وإريك دارف، آنيا(شمالسجل⁡شمال){\displaystyle {\mathcal {O}}(N\log N)}حل مباشر سريع للمصفوفات شبه المنفصلة الهرمية الجزئية، مجلة الحوسبة العلمية 57 (2013)، العدد  3، 477-501.
  32. ↑ ساكيت سوراب وميراڤ زهافي،(ك،ن-ك){\displaystyle (k,n-k)}-ماكس-كت: أنيا*(2ص){\displaystyle {\mathcal {O}}^{*}(2^{p})}- خوارزمية الوقت ونواة متعددة الحدود، Algorithmica 80 (2018)، رقم  12، 3844-3860.

ملحوظات

  1. لاحظ أن "حجم" المدخلات يُستخدم عادةً كمؤشر على مدى صعوبة حالة معينة من المشكلة المراد حلها. ويُنظر إلى مقدار وقت التنفيذ ومقدار مساحة الذاكرة المطلوبة لحساب الإجابة (أو "حل" المشكلة) على أنهما مؤشران على صعوبة تلك الحالة من المشكلة. ولأغراض نظرية التعقيد الحسابي ، فإن Bigيا{\displaystyle O}يتم استخدام الترميز للحد الأعلى على [رتبة المقدار] لجميع هذه الثلاثة: حجم [تدفق البيانات] المدخل، ومقدار وقت [التنفيذ] المطلوب، ومقدار مساحة [الذاكرة] المطلوبة.
  2. ↑ يُقترح هذا الاسم في عنوان ورقة بحثية لكنوت عام 1976، ولا يُعثر عليه في أي مكان آخر في بقية الورقة. نادرًا ما يُستخدم أو لا يُستخدم أبدًا.

للمزيد من القراءة

  • كنوت، دونالد (1997). "1.2.11: التمثيلات التقاربية". الخوارزميات الأساسية . فن برمجة الحاسوب. المجلد  1 (  الطبعة الثالثة). أديسون-ويسلي. ISBN 978-0-201-89683-1.
  • سيبسر، مايكل (1997). مقدمة في نظرية الحوسبة . دار نشر PWS. الصفحات 226-228 . ISBN  978-0-534-94728-6.
  • أفيغاد، جيريمي؛ دونيلي، كيفن (2004). صياغة رمز O في إيزابيل/هول (ملف PDF) . المؤتمر الدولي المشترك حول الاستدلال الآلي. doi : 10.1007/978-3-540-25984-8_27 .
  • بلاك، بول إي. (11 مارس 2005). بلاك، بول إي. (محرر). "ترميز Big-O" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . تم الاطلاع عليه في 16 ديسمبر 2006 .
  • بلاك، بول إي. (17 ديسمبر 2004). بلاك، بول إي. (محرر). "ترميز الحرف الصغير o" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . تم الاطلاع عليه في 16 ديسمبر 2006 .
  • بلاك، بول إي. (17 ديسمبر 2004). بلاك، بول إي. (محرر). "Ω" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . تم الاطلاع عليه في 16 ديسمبر 2006 .
  • بلاك، بول إي. (17 ديسمبر 2004). بلاك، بول إي. (محرر). "ω" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . تم الاطلاع عليه في 16 ديسمبر 2006 .
  • بلاك، بول إي. (17 ديسمبر 2004). بلاك، بول إي. (محرر). "Θ" . قاموس الخوارزميات وهياكل البيانات . المعهد الوطني الأمريكي للمعايير والتكنولوجيا . تم الاطلاع عليه في 16 ديسمبر 2006 .