اللوغاريتم المتكرر

في علم الحاسوب ، اللوغاريتم المتكرر لـ${\displaystyle n}$سجل مكتوب * ${\displaystyle n}$(يُقرأ عادةً " log star ")، وهو عدد المرات التي يجب فيها تطبيق دالة اللوغاريتم بشكل متكرر قبل أن تصبح النتيجة أقل من أو تساوي${\displaystyle 1}$[ ^{1 ]} أبسط تعريف رسمي هو نتيجة ^علاقة التكرار هذه :

${\displaystyle \log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}}$

في علوم الحاسوب، يُستخدم الرمز lg * غالبًا للإشارة إلى اللوغاريتم الثنائي المتكرر ، الذي يُكرر اللوغاريتم الثنائي (بأساس 1).${\displaystyle 2}$) بدلاً من اللوغاريتم الطبيعي (ذي الأساس e ). رياضياً، يكون اللوغاريتم المتكرر مُعرَّفاً جيداً لأي أساس أكبر من${\displaystyle e^{1/e}\approx 1.444667}$ليس فقط للقاعدة${\displaystyle 2}$والأساس e . دالة "اللوغاريتم الفائق".${\displaystyle \mathrm {slog} _{b}(n)}$هو "مكافئ بشكل أساسي" للأساس${\displaystyle b}$اللوغاريتم المتكرر (على الرغم من اختلافه في تفاصيل التقريب الطفيفة ) ويشكل معكوسًا لعملية التكرار . ^{[ 2 ]}

يُعد اللوغاريتم المتكرر مفيدًا في تحليل الخوارزميات والتعقيد الحسابي ، حيث يظهر في حدود التعقيد الزمني والمكاني لبعض الخوارزميات مثل:

• إيجاد تثليث ديلاوناي لمجموعة من النقاط بمعرفة الشجرة الممتدة الدنيا الإقليدية : وقت عشوائي O ( n log * n ). ^{[ 3 ]}  
• خوارزمية فورر لضرب الأعداد الصحيحة: O( n  log n 2 ^{O ( lg * n )} ).   
• إيجاد قيمة عظمى تقريبية (عنصر لا يقل حجمه عن الوسيط): lg * n − 1 ± 3 عمليات متوازية. ^{[ 4 ]} 
• خوارزمية ريتشارد كول وأوزي فيشكين الموزعة لتلوين دورة n بثلاثة ألوان : O ( log * n ) جولات اتصال متزامنة. ^{[ 5 ]} 

ينمو اللوغاريتم المتكرر بمعدل بطيء للغاية، أبطأ بكثير من اللوغاريتم نفسه أو تكراراته. وذلك لأن التكرار ينمو أسرع بكثير من الأسي المتكرر.

$${\displaystyle {^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}\gg \underbrace {b^{b^{\cdot ^{\cdot ^{b^{y}}}}}} _{n}}$$

أما العكس فينمو ببطء شديد:${\displaystyle \log _{b}^{*}x\ll \log _{b}^{n}x}$.

بالنسبة لجميع قيم n ذات الصلة بحساب أوقات تشغيل الخوارزميات المنفذة عمليًا (أي n  ≤  2 ⁶⁵⁵³⁶ ، وهو أكبر بكثير من العدد المقدر للذرات في الكون المعروف)، فإن اللوغاريتم المتكرر ذو الأساس 2 له قيمة لا تزيد عن 5.

تعطي القواعد الأعلى قيمًا أصغر للوغاريتمات المتكررة.

يرتبط اللوغاريتم المتكرر ارتباطًا وثيقًا بدالة اللوغاريتم المعمم المستخدمة في الحساب المتناظر ذي المؤشر المستوى . أما الاستمرارية الجمعية لعدد ما ، أي عدد المرات التي يجب فيها استبدال العدد بمجموع أرقامه قبل الوصول إلى جذره الرقمي ، فهي${\displaystyle O(\log ^{*}n)}$.

في نظرية التعقيد الحسابي ، يُبين سانثانام ^{[ 6 ]} أن الموارد الحسابية DTIME - زمن الحساب لآلة تورينج حتمية - و NTIME - زمن الحساب لآلة تورينج غير حتمية - متميزة حتى${\displaystyle n{\sqrt {\log ^{*}n}}.}$

• دالة أكرمان العكسية ، وهي دالة تنمو ببطء شديد، وتُستخدم أيضًا في نظرية التعقيد الحسابي.