الترميز L

يُعدّ ترميز L ترميزًا تقاربيًا مشابهًا لترميز Big-O ، ويُرمز إليه بـ${\displaystyle L_{n}[\alpha ,c]}$بالنسبة لمتغير مقيد${\displaystyle n}$يتجه إلى اللانهاية . ومثل ترميز Big-O، فإنه يستخدم عادة للتعبير بشكل تقريبي عن معدل نمو دالة ما ، مثل التعقيد الحسابي لخوارزمية معينة .

يُعرَّف بأنه

${\displaystyle L_{n}[\alpha ,c]=e^{(c+o(1))(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$

حيث c ثابت موجب، و${\displaystyle \alpha }$ثابت${\displaystyle 0\leq \alpha \leq 1}$.

يُستخدم ترميز L بشكل أساسي في نظرية الأعداد الحسابية ، للتعبير عن تعقيد الخوارزميات المستخدمة في مسائل نظرية الأعداد الصعبة، مثل المناخل المستخدمة في تحليل الأعداد الصحيحة إلى عواملها الأولية ، وطرق حل اللوغاريتمات المنفصلة . وتكمن فائدة هذا الترميز في أنه يُبسط تحليل هذه الخوارزميات.${\displaystyle e^{c(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$يعبّر عن المصطلح المهيمن، و ${\displaystyle e^{o(1)(\ln n)^{\alpha }(\ln \ln n)^{1-\alpha }}}$يهتم بكل شيء أصغر حجماً.

متى${\displaystyle \alpha }$إذا كانت القيمة صفرًا، فإن

${\displaystyle L_{n}[\alpha ,c]=L_{n[0,c]=e^{(c+o(1))\ln \ln n}=(\ln n)^{c+o(1)}\,}$

هي دالة متعددة اللوغاريتمات ( دالة متعددة الحدود لـ ln n )؛  

متى${\displaystyle \alpha }$إذا كان 1

${\displaystyle L_{n}[\alpha ,c]=L_{n}[1,c]=e^{(c+o(1))\ln n}=n^{c+o(1)}\,}$

هي دالة أسية كاملة لـ ln n (وبالتالي متعددة الحدود في n ). 

لو${\displaystyle \alpha }$إذا كانت القيمة بين 0 و 1، فإن الدالة تكون شبه أسية لـ ln n (ومتعددة الحدود الفائقة ). 

تتميز العديد من خوارزميات تحليل الأعداد الصحيحة العامة بتعقيد زمني شبه أسي . وأفضلها خوارزمية غربلة حقل الأعداد العامة ، والتي يبلغ زمن تشغيلها المتوقع 10 ...

${\displaystyle L_{n[1/3,c]=e^{(c+o(1))(\ln n)^{1/3}(\ln \ln n)^{2/3}}}$

ل${\displaystyle c=(64/9)^{1/3}\approx 1.923}$كانت أفضل خوارزمية من هذا النوع قبل غربال حقل الأعداد هي الغربال التربيعي الذي يتميز بوقت تشغيل

${\displaystyle L_{n[1/2,1]=e^{(1+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

ثالث أسرع طريقة معروفة لتحليل العوامل: تحليل منحنى لينسترا الإهليلجي ، والذي يبلغ وقت تشغيله

${\displaystyle L_{n[1/2,2^{1/2}]=e^{(2^{1/2}+o(1))(\ln n)^{1/2}(\ln \ln n)^{1/2}}.\,}$

بالنسبة لمسألة اللوغاريتم المنفصل للمنحنى الإهليلجي ، فإن أسرع خوارزمية عامة هي خوارزمية الخطوة الصغيرة والخطوة العملاقة ، والتي يبلغ زمن تشغيلها رتبة الجذر التربيعي لرتبة المجموعة n . في تدوين L، سيكون هذا

${\displaystyle L_{n[1,1/2]=n^{1/2+o(1)}.\,}$

إن وجود اختبار AKS للأعداد الأولية ، الذي يعمل في وقت متعدد الحدود ، يعني أن التعقيد الزمني لاختبار الأعداد الأولية معروف بأنه على الأكثر

${\displaystyle L_{n}[0,c]=(\ln n)^{c+o(1)}\,}$

حيث ثبت أن قيمة c لا تتجاوز 6. ^{[ 1 ]}

تم تعريف رمز L بأشكال مختلفة في الأدبيات. أول استخدام له كان من كارل بوميرانس في بحثه "تحليل ومقارنة بعض خوارزميات تحليل الأعداد الصحيحة إلى عواملها الأولية". ^{[ 2 ]} كان هذا الشكل يحتوي فقط على${\displaystyle c}$المعلمة: الـ${\displaystyle \alpha }$كانت الصيغة${\displaystyle 1/2}$بالنسبة للخوارزميات التي كان يحللها. كان بوميرانس يستخدم الرسالة${\displaystyle L}$(أو بأحرف صغيرة)${\displaystyle l}$) في هذه الورقة والأوراق السابقة للصيغ التي تتضمن العديد من اللوغاريتمات.

تم تقديم الصيغة المذكورة أعلاه، والتي تتضمن مُعاملين، من قِبل أرجين لينسترا وهندريك لينسترا في مقالتهما بعنوان "الخوارزميات في نظرية الأعداد". ^{[ 3 ]} وقد تم تقديمها في تحليلهما لخوارزمية اللوغاريتم المنفصل لكوبرسميث . وتُعد هذه الصيغة الأكثر شيوعًا في الأدبيات العلمية اليوم.

يُعرّف دليل التشفير التطبيقي رمز L بـ${\displaystyle O}$حول الصيغة المعروضة في هذه المقالة. ^{[ 4 ]} هذا ليس التعريف القياسي.${\displaystyle O}$قد يُشير ذلك إلى أن زمن التشغيل يُمثل حدًا أعلى. مع ذلك، بالنسبة لخوارزميات تحليل الأعداد الصحيحة إلى عواملها الأولية وخوارزميات اللوغاريتم المنفصل التي يُستخدم فيها ترميز L بشكل شائع، فإن زمن التشغيل لا يُمثل حدًا أعلى، لذا فإن هذا التعريف غير مُفضل.