The depth sequence starts from
$$d_0=0,\qquad d_1=x,$$
and then follows the nonlinear recurrence
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1).$$
An admissible drilling schedule must be strictly increasing, so the required condition is
$$d_0<d_1<d_2<\cdots.$$
The quantity to evaluate is
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
The C++, Python, and Java implementations all treat the answer as the boundary point of the upper admissible branch: they locate the smallest \(x\) in that branch and then evaluate \(C(x)\) there. Numerically, this boundary is near \(x_\star\approx 0.746542014027\), and the corresponding value is \(C(x_\star)\approx 2.364497769\).
Two identities make the search practical: one turns the monotonicity condition into a statement about successive gaps, and the other rewrites the objective as a rapidly convergent tail sum.
Define the forward gaps
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1).$$
The schedule is strictly increasing exactly when
$$\Delta_k>0\qquad \text{for all }k\ge 1.$$
From the recurrence we immediately get
$$d_{k+1}=e^{\Delta_k}.$$
For \(k\ge 2\), since \(d_k=e^{\Delta_{k-1}}\), the next gap satisfies
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}.$$
Because the exponential function is strictly increasing, this means
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2).$$
So admissibility is stronger than mere positivity: after the first two terms, the gap sequence must keep increasing as well.
For \(k\ge 2\), substitute the recurrence into one summand of \(C(x)\):
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
Therefore the cost becomes
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}.$$
Expanding the first few terms gives
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots.$$
This identity is very useful: once the depths become moderately large, the tail shrinks extremely fast.
Every finite prefix \(d_0,d_1,\dots,d_n\) depends continuously on the starting value \(x\). If one sampled value of \(x\) eventually produces a non-positive gap while a nearby value keeps all tested gaps positive, then a boundary point must lie between them.
The implementations exploit this by searching for the left edge of the upper admissible branch. Below that edge, some future gap becomes non-positive and strict increase fails. Above that edge, the simulated trajectory stays increasing and the depths quickly escape upward.
This is why bisection is appropriate: once a failing value and a succeeding value are bracketed, repeated midpoint testing isolates the smallest admissible \(x\) on that branch.
On the upper admissible branch, any smaller starting value is forbidden because it eventually breaks monotonicity. That makes the left boundary \(x_\star\) the natural candidate explored by the implementations.
The C++ implementation also checks a separated low admissible branch numerically and confirms that its sampled costs remain above the value found at the upper boundary. In other words, the final reported value comes from the smallest admissible \(x\) on the upper branch, not from a larger interior point.
Once some depth exceeds \(80\), every later tail term in
$$x+\sum_{j\ge 0} e^{-d_j}$$
is at most \(e^{-80}\approx 1.8\times 10^{-35}\). That is astronomically smaller than the \(10^{-9}\) precision of the printed answer. So the implementations can stop the simulation after the depth crosses \(80\), with a generous hard cap of \(200\) recurrence steps as a safety limit.
Take \(x=0.75\), which lies very close to the upper-branch boundary used by the implementations. The first depths are
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
The cost identity now gives
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
This already sits very close to the boundary value reported by the implementations, and it shows how quickly the tail becomes negligible.
The C++, Python, and Java implementations all simulate the recurrence directly from \(d_0=0\) and a trial value of \(d_1=x\). During this simulation they check the gap \(d_k-d_{k-1}\) at each step, and they reject the trial immediately if any gap becomes non-positive.
To locate the upper admissible branch, the implementations first perform a coarse scan on the interval \(0.6\le x\le 1.5\) with step \(0.01\). This finds the first transition from failure to success on that branch.
After bracketing the transition, they run \(90\) bisection iterations. The midpoint is tested by the same recurrence simulation, so the boundary estimate tightens until the desired floating-point precision is reached.
Once the boundary value has been isolated, the implementations replay the recurrence and accumulate the cost. They stop when the depth exceeds \(80\), because the remaining tail is far below the displayed precision.
The C++ implementation adds extra sanity checks around the boundary and compares against sampled points on the low branch, while the Python and Java implementations keep only the core search-and-evaluate procedure.
Let \(T\) be the maximum number of recurrence steps used in a single simulation. Here \(T\le 200\). One admissibility test or one cost evaluation therefore costs \(O(T)\) time and \(O(1)\) memory.
If the coarse scan uses \(S\) samples and the refinement uses \(B\) bisection steps, the total running time is
$$O((S+B)T).$$
Since \(B=O(\log(1/\varepsilon))\) for target precision \(\varepsilon\), this is also \(O(T\log(1/\varepsilon))\) once the initial scan interval is fixed. Because all constants are small and fixed in the implementations, the practical runtime is effectively constant and the memory usage remains \(O(1)\).
Die Tiefenfolge beginnt mit
$$d_0=0,\qquad d_1=x,$$
und erfüllt danach die nichtlineare Rekursion
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1).$$
Ein zulässiger Bohrplan muss streng wachsen, also gilt
$$d_0<d_1<d_2<\cdots.$$
Ausgewertet wird
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
Die C++-, Python- und Java-Implementierungen behandeln die gesuchte Lösung als Randpunkt des oberen zulässigen Astes: Sie bestimmen das kleinste \(x\) auf diesem Ast und berechnen dort \(C(x)\). Numerisch liegt dieser Rand bei \(x_\star\approx 0.746542014027\), und der zugehörige Wert ist \(C(x_\star)\approx 2.364497769\).
Zwei Umformungen machen das Problem handhabbar: Die erste beschreibt Monotonie über aufeinanderfolgende Abstände, die zweite schreibt die Zielfunktion als schnell konvergierende Summe um.
Definiere die Vorwärtsdifferenzen
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1).$$
Strenges Wachstum ist genau äquivalent zu
$$\Delta_k>0\qquad \text{für alle }k\ge 1.$$
Aus der Rekursion folgt sofort
$$d_{k+1}=e^{\Delta_k}.$$
Für \(k\ge 2\) gilt wegen \(d_k=e^{\Delta_{k-1}}\) außerdem
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}.$$
Da die Exponentialfunktion streng monoton wächst, erhält man
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2).$$
Damit ist Zulässigkeit stärker als reine Positivität: Nach den ersten beiden Schritten müssen die Abstände selbst weiter anwachsen.
Für \(k\ge 2\) kann man einen Summanden von \(C(x)\) direkt vereinfachen:
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
Daraus folgt
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}.$$
Die ersten Terme lauten also
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots.$$
Diese Darstellung zeigt sofort, warum der Rest der Summe nach einigen Schritten verschwindend klein wird.
Jedes endliche Präfix \(d_0,d_1,\dots,d_n\) hängt stetig von \(x\) ab. Wenn ein Testwert von \(x\) irgendwann eine nichtpositive Lücke erzeugt, ein naher Wert aber alle getesteten Lücken positiv hält, dann muss dazwischen ein Randwert liegen.
Die Implementierungen suchen genau den linken Rand des oberen zulässigen Astes. Unterhalb dieses Randes wird irgendwann eine Lücke nichtpositiv und das strenge Wachstum bricht zusammen. Oberhalb davon bleibt die simulierte Folge wachsend und die Tiefen laufen rasch nach oben weg.
Darum passt Bisektion hier gut: Sobald ein unzulässiger und ein zulässiger Wert eingeklammert sind, kann man den kleinsten zulässigen Startwert auf diesem Ast durch Mittelpunkttests isolieren.
Auf dem oberen zulässigen Ast sind kleinere Startwerte verboten, weil sie die Monotonie irgendwann verletzen. Deshalb ist der linke Rand \(x_\star\) der natürliche Kandidat, den die Implementierungen auswerten.
Die C++-Implementierung prüft zusätzlich numerisch einen getrennten unteren zulässigen Ast und bestätigt, dass dessen Stichprobenkosten über dem Wert am oberen Rand bleiben. Der ausgegebene Wert stammt also vom kleinsten zulässigen \(x\) des oberen Astes und nicht von einem größeren inneren Punkt.
Sobald eine Tiefe \(80\) überschreitet, ist jeder spätere Summand in
$$x+\sum_{j\ge 0} e^{-d_j}$$
höchstens \(e^{-80}\approx 1.8\times 10^{-35}\). Das liegt weit unter der Ausgabegenauigkeit von \(10^{-9}\). Deshalb können die Implementierungen nach Überschreiten von \(80\) abbrechen; eine Obergrenze von \(200\) Rekursionsschritten dient nur als Sicherheitsnetz.
Nimm \(x=0.75\), also einen Wert sehr nahe am oberen Rand. Dann sind die ersten Tiefen
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
Mit der umgeschriebenen Zielfunktion erhält man
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
Das liegt bereits sehr nahe am endgültigen Randwert und illustriert die schnelle Konvergenz.
Die C++-, Python- und Java-Implementierungen simulieren die Rekursion direkt ausgehend von \(d_0=0\) und einem Testwert \(d_1=x\). Bei jedem Schritt prüfen sie die Lücke \(d_k-d_{k-1}\) und verwerfen den Testwert sofort, sobald eine Lücke nichtpositiv wird.
Um den oberen zulässigen Ast zu finden, wird zuerst das Intervall \(0.6\le x\le 1.5\) mit Schrittweite \(0.01\) grob abgesucht. So findet man den ersten Übergang von Fehlschlag zu Erfolg auf diesem Ast.
Danach folgen \(90\) Bisektionsschritte. Der jeweilige Mittelpunkt wird wieder durch dieselbe Rekursionssimulation getestet, bis die gewünschte Gleitkommapräzision erreicht ist.
Anschließend wird die Rekursion erneut durchlaufen und die Kosten werden aufsummiert. Sobald eine Tiefe größer als \(80\) ist, endet die Berechnung, weil der Rest der Reihe numerisch vernachlässigbar ist.
Die C++-Implementierung ergänzt noch Plausibilitätsprüfungen am Rand und vergleicht mit Stichproben des unteren Astes; die Python- und Java-Implementierungen beschränken sich auf die Kernsuche und die Endauswertung.
Sei \(T\) die maximale Zahl von Rekursionsschritten innerhalb einer einzelnen Simulation. Hier gilt \(T\le 200\). Ein Monotonietest oder eine Kostenauswertung benötigt also \(O(T)\) Zeit und \(O(1)\) Speicher.
Verwendet die Grobsuche \(S\) Stichproben und die Verfeinerung \(B\) Bisektionsschritte, so ist die Gesamtlaufzeit
$$O((S+B)T).$$
Mit \(B=O(\log(1/\varepsilon))\) für Zielgenauigkeit \(\varepsilon\) ergibt sich äquivalent \(O(T\log(1/\varepsilon))\), sobald das Startintervall fest vorgegeben ist. Da alle Konstanten klein und fest sind, ist die praktische Laufzeit effektiv konstant, und der Speicherbedarf bleibt \(O(1)\).
Derinlik dizisi
$$d_0=0,\qquad d_1=x,$$
ile başlar ve sonra
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1)$$
yinelemesini izler. Geçerli bir sondaj planı sıkı artan olmalıdır; yani
$$d_0<d_1<d_2<\cdots$$
koşulu gerekir. Değerlendirilen büyüklük ise
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
C++, Python ve Java implementasyonları cevabı üst geçerli dalın sınır noktası olarak ele alır: o daldaki en küçük \(x\) bulunur ve \(C(x)\) orada hesaplanır. Sayısal olarak bu sınır \(x_\star\approx 0.746542014027\) civarındadır ve karşılık gelen değer \(C(x_\star)\approx 2.364497769\) olur.
Aramayı uygulanabilir hale getiren iki temel özdeşlik vardır: biri monotonluk koşulunu ardışık farklar üzerinden yazar, diğeri de amaç fonksiyonunu çok hızlı yakınsayan bir kuyruk toplamına dönüştürür.
İleri farkları
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1)$$
şeklinde tanımlayalım. Dizi ancak ve ancak
$$\Delta_k>0\qquad \text{tüm }k\ge 1\text{ için}$$
olduğunda sıkı artandır. Yinelemeden doğrudan
$$d_{k+1}=e^{\Delta_k}$$
elde edilir. Ayrıca \(k\ge 2\) için \(d_k=e^{\Delta_{k-1}}\) olduğundan
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}$$
yazabiliriz. Üstel fonksiyon sıkı artan olduğu için
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2)$$
sonucu çıkar. Yani geçerlilik yalnızca farkların pozitif kalmasını değil, ilk birkaç adımdan sonra kendi aralarında da artmasını gerektirir.
\(k\ge 2\) için bir terimi yineleme ile sadeleştirebiliriz:
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
Böylece maliyet
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}$$
şeklini alır. İlk terimler açıkça
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots$$
olur. Bu yazım, derinlikler büyüdükçe toplam kuyruğunun neden son derece küçüldüğünü açıkça gösterir.
Her sonlu önek \(d_0,d_1,\dots,d_n\), başlangıç değeri \(x\)'e sürekli bağlıdır. Bir örnek \(x\) ileride negatif ya da sıfır fark üretirken yakın bir başka \(x\) tüm test edilen farkları pozitif tutuyorsa, arada bir sınır değeri bulunmak zorundadır.
Implementasyonlar tam olarak üst geçerli dalın sol ucunu arar. Bu sınırın altında gelecekte bir fark pozitifliğini kaybeder ve sıkı artış bozulur. Sınırın üstünde ise simülasyon artan kalır ve derinlikler hızla yukarı kaçar.
Bu yüzden ikili arama uygundur: başarısız bir değer ile başarılı bir değer arasında sıkışan sınır, orta nokta testleriyle hassas biçimde bulunabilir.
Üst geçerli dal üzerinde daha küçük başlangıç değerlerine inmek mümkün değildir; çünkü bir noktada monotonluk bozulur. Bu nedenle sol sınır \(x_\star\), implementasyonların doğal aday noktasıdır.
C++ implementasyonu ayrıca ayrık bir alt geçerli dalı sayısal olarak örnekler ve oradaki maliyetlerin, üst sınırda bulunan değerden daha küçük olmadığını kontrol eder. Yani raporlanan sonuç, üst dalın en küçük geçerli \(x\) değerinden gelir.
Bir derinlik \(80\)'i geçtiğinde
$$x+\sum_{j\ge 0} e^{-d_j}$$
toplamındaki sonraki her terim en fazla \(e^{-80}\approx 1.8\times 10^{-35}\) olur. Bu değer, yazdırılan \(10^{-9}\) hassasiyetin çok altındadır. Bu yüzden implementasyonlar derinlik \(80\)'i aştığında durabilir; \(200\) adımlık üst sınır ise sadece ek güvenlik payıdır.
\(x=0.75\) alalım; bu değer implementasyonların kullandığı üst sınır noktasına oldukça yakındır. İlk derinlikler
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
Maliyet özdeşliğiyle
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
Bu değer son cevaba oldukça yakındır ve kuyruğun ne kadar hızlı söndüğünü gösterir.
C++, Python ve Java implementasyonları yinelemeyi doğrudan \(d_0=0\) ve deneme değeri \(d_1=x\) üzerinden simüle eder. Her adımda \(d_k-d_{k-1}\) farkını kontrol ederler; fark sıfır ya da negatif olursa aday hemen reddedilir.
Üst geçerli dalı bulmak için önce \(0.6\le x\le 1.5\) aralığında \(0.01\) adımlı kaba bir tarama yapılır. Böylece bu dal üzerindeki ilk başarısızlık-başarı geçişi bulunur.
Ardından \(90\) tur ikili arama uygulanır. Her orta nokta aynı yineleme ile test edildiği için sınır değeri kayan nokta hassasiyetine kadar daraltılır.
Sınır bulunduktan sonra yineleme tekrar oynatılır ve maliyet toplanır. Derinlik \(80\)'i geçtiğinde işlem durdurulur; çünkü kalan terimler basılan hassasiyet açısından ihmal edilebilir düzeydedir.
C++ implementasyonu buna ek olarak sınırın çevresinde doğrulamalar yapar ve alt dal örnekleriyle karşılaştırır. Python ve Java implementasyonları ise yalnızca temel arama ve hesaplama adımlarını içerir.
Tek bir simülasyonda kullanılan en fazla yineleme adımı sayısına \(T\) diyelim. Burada \(T\le 200\). Buna göre tek bir geçerlilik testi ya da maliyet hesabı \(O(T)\) zaman ve \(O(1)\) bellek kullanır.
Kaba tarama \(S\) örnek, rafine etme de \(B\) ikili arama adımı kullanıyorsa toplam süre
$$O((S+B)T)$$
olur. Hedef doğruluk \(\varepsilon\) cinsinden \(B=O(\log(1/\varepsilon))\) olduğundan, başlangıç aralığı sabit kabul edildiğinde bu aynı zamanda \(O(T\log(1/\varepsilon))\) biçiminde yazılabilir. Sabitler küçük ve sabit olduğu için pratikte çalışma süresi fiilen sabittir; bellek tüketimi de \(O(1)\) kalır.
La sucesión de profundidades comienza con
$$d_0=0,\qquad d_1=x,$$
y luego sigue la recurrencia no lineal
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1).$$
Un plan admisible debe ser estrictamente creciente, así que se exige
$$d_0<d_1<d_2<\cdots.$$
La cantidad que se evalúa es
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
Las implementaciones en C++, Python y Java tratan la respuesta como el punto de borde de la rama admisible superior: localizan el menor \(x\) de esa rama y evalúan allí \(C(x)\). Numéricamente, ese borde está cerca de \(x_\star\approx 0.746542014027\), y el valor correspondiente es \(C(x_\star)\approx 2.364497769\).
Dos identidades sencillas vuelven manejable la búsqueda: una convierte la condición de monotonía en una condición sobre diferencias sucesivas, y la otra reescribe el objetivo como una suma de cola que converge muy deprisa.
Definimos las diferencias hacia adelante
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1).$$
La sucesión es estrictamente creciente exactamente cuando
$$\Delta_k>0\qquad \text{para todo }k\ge 1.$$
La recurrencia da inmediatamente
$$d_{k+1}=e^{\Delta_k}.$$
Para \(k\ge 2\), como \(d_k=e^{\Delta_{k-1}}\), también tenemos
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}.$$
Como la función exponencial es estrictamente creciente, se concluye que
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2).$$
Por tanto, la admisibilidad no solo exige diferencias positivas: después de los primeros pasos, las diferencias mismas deben seguir creciendo.
Para \(k\ge 2\), un término de \(C(x)\) se simplifica así:
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
Entonces
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}.$$
Los primeros términos quedan
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots.$$
Esta forma explica por qué la cola se vuelve diminuta en cuanto las profundidades crecen un poco.
Cada prefijo finito \(d_0,d_1,\dots,d_n\) depende continuamente del valor inicial \(x\). Si un valor de \(x\) termina produciendo una diferencia no positiva, mientras que otro valor cercano mantiene todas las diferencias probadas positivas, entonces debe existir un punto frontera entre ambos.
Las implementaciones buscan exactamente el borde izquierdo de la rama admisible superior. Por debajo de ese borde, alguna diferencia futura deja de ser positiva y falla el crecimiento estricto. Por encima, la trayectoria simulada sigue siendo creciente y las profundidades escapan rápidamente hacia arriba.
Por eso la bisección es adecuada: una vez acotados un valor que falla y otro que funciona, las pruebas en el punto medio aíslan el menor \(x\) admisible de esa rama.
En la rama admisible superior no se puede bajar a valores iniciales menores, porque tarde o temprano se rompe la monotonía. Eso convierte al borde izquierdo \(x_\star\) en el candidato natural que exploran las implementaciones.
La implementación en C++ también muestrea numéricamente una rama admisible baja y verifica que sus costes muestrales siguen estando por encima del valor obtenido en el borde superior. Así, el resultado final proviene del menor \(x\) admisible de la rama superior.
Cuando alguna profundidad supera \(80\), cada término posterior en
$$x+\sum_{j\ge 0} e^{-d_j}$$
es a lo sumo \(e^{-80}\approx 1.8\times 10^{-35}\). Eso está muchísimo más abajo que la precisión impresa de \(10^{-9}\). Por tanto, las implementaciones pueden detenerse cuando la profundidad pasa de \(80\), manteniendo además un límite duro de \(200\) pasos como salvaguarda.
Tomemos \(x=0.75\), muy cercano al borde superior que usan las implementaciones. Las primeras profundidades son
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
La identidad del coste da
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
Ya está muy cerca del valor final y muestra cuán rápido desaparece la cola.
Las implementaciones en C++, Python y Java simulan directamente la recurrencia a partir de \(d_0=0\) y un valor de prueba \(d_1=x\). En cada paso revisan la diferencia \(d_k-d_{k-1}\) y rechazan el candidato en cuanto esa diferencia se vuelve no positiva.
Para localizar la rama admisible superior, primero hacen un barrido grueso sobre \(0.6\le x\le 1.5\) con paso \(0.01\). Así encuentran la primera transición de fallo a éxito en esa rama.
Después ejecutan \(90\) iteraciones de bisección. El punto medio se comprueba con la misma simulación, de modo que la estimación del borde se refina hasta la precisión deseada.
Una vez aislado el borde, vuelven a recorrer la recurrencia y acumulan el coste. Se detienen cuando la profundidad supera \(80\), porque el resto de la serie es insignificante frente a la precisión mostrada.
La versión en C++ añade comprobaciones de consistencia alrededor del borde y compara con puntos muestreados de la rama baja; las versiones en Python y Java conservan solo el núcleo de búsqueda y evaluación.
Sea \(T\) el número máximo de pasos de recurrencia en una sola simulación. Aquí \(T\le 200\). Una prueba de admisibilidad o una evaluación del coste requiere entonces \(O(T)\) tiempo y \(O(1)\) memoria.
Si el barrido grueso usa \(S\) muestras y el refinamiento usa \(B\) pasos de bisección, el tiempo total es
$$O((S+B)T).$$
Como \(B=O(\log(1/\varepsilon))\) para una precisión objetivo \(\varepsilon\), esto también puede escribirse como \(O(T\log(1/\varepsilon))\) una vez fijado el intervalo inicial. En la práctica, todas las constantes son pequeñas y fijas, así que el tiempo efectivo es esencialmente constante y la memoria sigue siendo \(O(1)\).
深度序列从
$$d_0=0,\qquad d_1=x$$
开始，并满足非线性递推
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1)$$
可接受的钻井方案必须严格递增，因此要求
$$d_0<d_1<d_2<\cdots$$
需要计算的量是
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}$$
C++、Python 和 Java 实现都把答案视为“上方可行分支”的边界点：先找到该分支中最小的可行 \(x\)，再在该点计算 \(C(x)\)。数值上，这个边界约为 \(x_\star\approx 0.746542014027\)，对应的结果约为 \(C(x_\star)\approx 2.364497769\)。
这个问题之所以可以直接数值处理，是因为有两个关键恒等式：第一个把单调性条件改写成相邻间隙的条件，第二个把目标函数改写成一个收敛极快的尾和。
定义前向间隙
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1)$$
序列严格递增，当且仅当
$$\Delta_k>0\qquad \text{对所有 }k\ge 1\text{ 成立。}$$
由递推式立刻得到
$$d_{k+1}=e^{\Delta_k}$$
对 \(k\ge 2\)，又因为 \(d_k=e^{\Delta_{k-1}}\)，于是
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}$$
指数函数严格递增，所以有
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2)$$
这说明可行性不只是“所有差值为正”这么简单。进入后续阶段以后，间隙本身也必须继续增大；一旦某一步出现 \(\Delta_k\le 0\)，严格递增立即失效。
对 \(k\ge 2\)，把递推式代入目标函数中的一个项：
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}$$
因此整个目标可以改写为
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}$$
把前几项展开就是
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots$$
这个式子非常重要，因为它直接解释了为什么只要深度稍微变大一些，后面的尾项就会迅速小到可以忽略。
对任意固定的步数 \(n\)，有限前缀 \(d_0,d_1,\dots,d_n\) 都是初始值 \(x\) 的连续函数。于是，如果一个采样点最终会出现非正间隙，而附近另一个采样点在所有测试步内都保持正间隙，那么两者之间必然存在一个边界值。
实现所寻找的，正是上方可行分支的左边界。低于这个边界时，未来某个间隙会失去正性，严格递增被破坏；高于这个边界时，模拟轨道保持递增，而且深度会很快向上发散。
因此二分搜索是自然选择：只要先用一个失败点和一个成功点把边界夹住，就可以不断测试中点，把该分支中最小的可行 \(x\) 精确逼近出来。
在上方可行分支内部，任何比边界更小的起始值都会在某个时刻破坏单调性，因此根本不允许。这样一来，左边界 \(x_\star\) 就成为实现自然需要评估的候选点。
C++ 实现还额外对下方的另一段可行分支做了数值抽样，并确认那一段的采样成本都高于上方边界处得到的值。也就是说，最终输出来自上方分支中最小的可行起点，而不是更大的内部点。
一旦某个深度超过 \(80\)，那么在
$$x+\sum_{j\ge 0} e^{-d_j}$$
中的每一个后续尾项都不会超过 \(e^{-80}\approx 1.8\times 10^{-35}\)。这个量比最终输出保留的 \(10^{-9}\) 精度小了很多个数量级，所以在深度越过 \(80\) 后停止计算是完全安全的。实现里再加一个 \(200\) 步的硬上限，只是为了防御性控制。
取 \(x=0.75\)，它非常接近实现最终使用的上方边界。前几项深度为
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700 \end{aligned}$$
利用上面的恒等式，成本可以写成
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648 \end{aligned}$$
只看前几项就已经非常接近最终数值，这也说明为什么尾和可以很早就截断。
C++、Python 和 Java 实现都直接从 \(d_0=0\) 和试探值 \(d_1=x\) 开始模拟递推。每前进一步都检查当前间隙 \(d_k-d_{k-1}\)；只要出现非正值，这个 \(x\) 就被立刻判定为不可行。
为了定位上方可行分支，程序先在 \(0.6\le x\le 1.5\) 上用步长 \(0.01\) 做粗扫描，找出该分支上第一次从“不行”变成“可行”的位置。
得到这个包围区间后，再进行 \(90\) 次二分。每个中点都用同样的递推模拟来检测，因此边界值会稳定收敛到浮点精度允许的范围内。
边界确定后，程序用同一条轨道重新累计 \(C(x)\)。当深度超过 \(80\) 时就停止，因为后续贡献已经远小于显示精度。
C++ 版本还加入了额外的边界检查，并和下方分支上的若干采样点做比较；Python 与 Java 版本则保留了最核心的搜索与求值流程。
设单次模拟最多使用 \(T\) 个递推步。在这里 \(T\le 200\)。因此一次可行性测试或一次成本计算都需要 \(O(T)\) 时间和 \(O(1)\) 额外空间。
如果粗扫描使用 \(S\) 个采样点，二分细化使用 \(B\) 次，那么总时间复杂度是
$$O((S+B)T)$$
把目标精度记为 \(\varepsilon\) 时，由于 \(B=O(\log(1/\varepsilon))\)，在初始扫描区间固定的前提下，也可以写成 \(O(T\log(1/\varepsilon))\)。由于实现中的各个常数都很小且固定，实际运行时间几乎就是常数级，空间始终为 \(O(1)\)。
Последовательность глубин начинается с
$$d_0=0,\qquad d_1=x,$$
а затем удовлетворяет нелинейной рекурсии
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1).$$
Допустимый план бурения должен быть строго возрастающим, то есть требуется
$$d_0<d_1<d_2<\cdots.$$
Вычисляется величина
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
Реализации на C++, Python и Java рассматривают ответ как граничную точку верхней допустимой ветви: они находят на этой ветви минимальное \(x\) и вычисляют там \(C(x)\). Численно эта граница лежит около \(x_\star\approx 0.746542014027\), а соответствующее значение равно \(C(x_\star)\approx 2.364497769\).
Практичность решения обеспечивают два преобразования: первое выражает условие монотонности через последовательность зазоров, а второе переписывает целевую функцию как быстро затухающую хвостовую сумму.
Введем разности
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1).$$
Строгое возрастание эквивалентно условию
$$\Delta_k>0\qquad \text{для всех }k\ge 1.$$
Из рекурсии сразу следует
$$d_{k+1}=e^{\Delta_k}.$$
Для \(k\ge 2\), поскольку \(d_k=e^{\Delta_{k-1}}\), получаем
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}.$$
Так как экспонента строго возрастает, имеем
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2).$$
Значит, допустимость требует не только положительности разностей: после первых шагов сами зазоры тоже должны последовательно расти.
Для \(k\ge 2\) один член суммы упрощается так:
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
Следовательно,
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}.$$
Первые члены выглядят так:
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots.$$
Эта форма сразу показывает, почему хвост ряда становится практически нулевым, как только глубины начинают быстро расти.
Любой конечный префикс \(d_0,d_1,\dots,d_n\) непрерывно зависит от начального значения \(x\). Если один пробный \(x\) в какой-то момент дает неположительный зазор, а близкий к нему другой \(x\) сохраняет все проверенные зазоры положительными, то между ними должен существовать граничный параметр.
Реализации ищут именно левую границу верхней допустимой ветви. Ниже этой границы некоторый будущий зазор теряет положительность, и строгое возрастание рушится. Выше границы траектория остается возрастающей, а глубины быстро уходят вверх.
Поэтому метод бисекции здесь естественен: после того как найдено одно неудачное и одно удачное значение, середины отрезка последовательно изолируют минимальное допустимое \(x\) на данной ветви.
На верхней допустимой ветви уйти к меньшему стартовому значению нельзя: рано или поздно монотонность будет нарушена. Значит, левая граница \(x_\star\) становится естественным кандидатом, который и оценивают реализации.
Реализация на C++ дополнительно делает численную проверку нижней допустимой ветви и убеждается, что ее выборочные стоимости остаются выше значения, найденного на верхней границе. Поэтому финальный результат берется именно из минимального допустимого \(x\) верхней ветви.
Как только какая-то глубина превышает \(80\), каждый следующий хвостовой член в
$$x+\sum_{j\ge 0} e^{-d_j}$$
не превосходит \(e^{-80}\approx 1.8\times 10^{-35}\). Это на много порядков меньше требуемой точности \(10^{-9}\). Поэтому реализации могут останавливать суммирование после пересечения уровня \(80\); ограничение в \(200\) шагов служит лишь дополнительной страховкой.
Возьмем \(x=0.75\), то есть значение, очень близкое к верхней границе, используемой реализациями. Первые глубины равны
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
Тогда по переписанной формуле стоимости
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
Уже несколько первых членов дают значение, очень близкое к итоговому, что хорошо показывает быстроту сходимости.
Реализации на C++, Python и Java напрямую моделируют рекурсию, начиная с \(d_0=0\) и пробного значения \(d_1=x\). На каждом шаге проверяется разность \(d_k-d_{k-1}\); если она становится неположительной, кандидат сразу отвергается.
Чтобы найти верхнюю допустимую ветвь, сначала выполняется грубое сканирование на интервале \(0.6\le x\le 1.5\) с шагом \(0.01\). Так находится первый переход от неудачи к успеху на этой ветви.
После этого запускаются \(90\) шагов бисекции. Каждая середина интервала снова проверяется той же симуляцией, поэтому оценка границы быстро сужается до нужной точности.
Когда граница найдена, рекурсия проигрывается еще раз, и параллельно накапливается стоимость. При достижении глубины выше \(80\) вычисление останавливается, потому что оставшийся хвост уже намного меньше печатаемой точности.
Версия на C++ добавляет дополнительные проверки около границы и сравнение с выборкой на нижней ветви, тогда как версии на Python и Java оставляют только основной цикл поиска и вычисления.
Пусть \(T\) обозначает максимальное число шагов рекурсии в одной симуляции. Здесь \(T\le 200\). Тогда одна проверка допустимости или одно вычисление стоимости требует \(O(T)\) времени и \(O(1)\) памяти.
Если грубое сканирование использует \(S\) пробных значений, а уточнение использует \(B\) шагов бисекции, суммарное время равно
$$O((S+B)T).$$
Поскольку \(B=O(\log(1/\varepsilon))\) для требуемой точности \(\varepsilon\), это также можно записать как \(O(T\log(1/\varepsilon))\) при фиксированном стартовом интервале. На практике все константы малы и заранее заданы, так что время работы фактически постоянно, а память остается \(O(1)\).
تبدأ متتالية الأعماق بـ
$$d_0=0,\qquad d_1=x,$$
ثم تتبع العلاقة التراجعية غير الخطية
$$d_{k+1}=e^{d_k-d_{k-1}}\qquad (k\ge 1).$$
ويجب أن يكون برنامج الحفر المقبول متزايدًا تزايدًا صارمًا، أي لا بد من تحقق
$$d_0<d_1<d_2<\cdots.$$
أما الكمية المطلوب تقييمها فهي
$$C(x)=\sum_{k\ge 1} d_k e^{-d_{k-1}}.$$
تتعامل تطبيقات C++ وPython وJava مع الجواب على أنه نقطة الحد الفاصل للفرع المقبول العلوي: فهي تجد أصغر \(x\) على ذلك الفرع ثم تحسب \(C(x)\) عنده. عدديًا يقع هذا الحد قرب \(x_\star\approx 0.746542014027\)، والقيمة الموافقة هي \(C(x_\star)\approx 2.364497769\).
هناك هويتان أساسيتان تجعلـان المسألة قابلة للمعالجة العددية المباشرة: الأولى تعيد صياغة شرط التزايد عبر فروق متتالية، والثانية تعيد كتابة دالة الهدف على صورة مجموع ذيل يتضاءل بسرعة كبيرة.
لنعرّف الفروق الأمامية
$$\Delta_k=d_k-d_{k-1}\qquad (k\ge 1).$$
يكون المسار متزايدًا تزايدًا صارمًا إذا وفقط إذا تحقق
$$\Delta_k>0\qquad (\forall k\ge 1).$$
ومن العلاقة الأصلية نحصل مباشرة على
$$d_{k+1}=e^{\Delta_k}.$$
ولـ \(k\ge 2\)، وبما أن \(d_k=e^{\Delta_{k-1}}\)، فإن
$$\Delta_{k+1}=d_{k+1}-d_k=e^{\Delta_k}-e^{\Delta_{k-1}}.$$
وبما أن الدالة الأسية متزايدة تمامًا، فهذا يعطي
$$\Delta_{k+1}>0 \iff \Delta_k>\Delta_{k-1}\qquad (k\ge 2).$$
إذًا شرط القبول أقوى من مجرد بقاء الفروق موجبة؛ فبعد الخطوات الأولى يجب أن تستمر الفروق نفسها في الازدياد أيضًا.
بالنسبة إلى \(k\ge 2\)، يمكن تبسيط حد واحد من \(C(x)\) كما يلي:
$$d_k e^{-d_{k-1}}=e^{d_{k-1}-d_{k-2}}e^{-d_{k-1}}=e^{-d_{k-2}}.$$
ومن ثم يصبح
$$C(x)=x+\sum_{k\ge 2} e^{-d_{k-2}}=x+\sum_{j\ge 0} e^{-d_j}.$$
وبتوسيع الحدود الأولى نحصل على
$$C(x)=x+1+e^{-x}+e^{-e^x}+e^{-d_3}+e^{-d_4}+\cdots.$$
هذه الصيغة تشرح مباشرة لماذا يصبح الذيل عديم الأثر تقريبًا عندما تبدأ الأعماق بالازدياد بسرعة.
كل بادئة منتهية \(d_0,d_1,\dots,d_n\) تعتمد بصورة مستمرة على القيمة الابتدائية \(x\). فإذا كانت قيمة معيّنة من \(x\) تنتج في مرحلة لاحقة فرقًا غير موجب، بينما تبقي قيمة قريبة منها جميع الفروق المختبرة موجبة، فلا بد من وجود قيمة حدية بينهما.
تبحث التطبيقات تحديدًا عن الحافة اليسرى للفرع المقبول العلوي. تحت هذه الحافة يفقد أحد الفروق المستقبلية موجبـيته فينهار شرط التزايد الصارم. وفوقها يبقى المسار المتولد متزايدًا، ثم تنطلق الأعماق سريعًا نحو قيم كبيرة.
ولهذا يكون البحث الثنائي مناسبًا: ما دام لدينا طرف فاشل وطرف ناجح، فإن اختبار المنتصف مرارًا يعزل أصغر \(x\) مقبول على ذلك الفرع.
على الفرع المقبول العلوي لا يمكن النزول إلى قيمة ابتدائية أصغر، لأن التزايد الصارم سينكسر في مرحلة ما. لذا تصبح الحافة اليسرى \(x_\star\) هي المرشح الطبيعي الذي تقيمه التطبيقات.
وتجري نسخة C++ فحصًا عدديًا إضافيًا لفرع سفلي منفصل، وتؤكد أن تكاليفه المأخوذة بالعينة تبقى أعلى من القيمة المحسوبة عند الحافة العلوية. لذلك فإن النتيجة النهائية مأخوذة من أصغر \(x\) مقبول على الفرع العلوي.
بمجرد أن يتجاوز أحد الأعماق القيمة \(80\)، فإن كل حد لاحق في
$$x+\sum_{j\ge 0} e^{-d_j}$$
يصبح على الأكثر \(e^{-80}\approx 1.8\times 10^{-35}\). وهذا أصغر بكثير من دقة الإخراج \(10^{-9}\). لذلك يمكن إيقاف الحساب عندما يتجاوز العمق \(80\)، مع الإبقاء على حد أقصى مقداره \(200\) خطوة كإجراء احتياطي فقط.
لنأخذ \(x=0.75\)، وهي قيمة قريبة جدًا من الحافة العلوية التي تعتمدها التطبيقات. عندئذ تكون الأعماق الأولى
$$\begin{aligned} d_0&=0,\\ d_1&=0.75,\\ d_2&=e^{0.75}\approx 2.117000017,\\ d_3&=e^{2.117000017-0.75}\approx 3.923562400,\\ d_4&=e^{3.923562400-2.117000017}\approx 6.089478119,\\ d_5&=e^{6.089478119-3.923562400}\approx 8.722585700. \end{aligned}$$
وباستخدام صيغة الكلفة المعاد كتابتها نحصل على
$$\begin{aligned} C(0.75)&=0.75+1+e^{-0.75}+e^{-2.117000017}+e^{-3.923562400}+e^{-6.089478119}+\cdots\\ &\approx 0.75+1+0.472366553+0.120392262+0.019770539+0.002266591+\cdots\\ &\approx 2.3648. \end{aligned}$$
وهذه القيمة قريبة جدًا من النتيجة النهائية، كما توضح مدى سرعة اضمحلال الذيل.
تقوم تطبيقات C++ وPython وJava بمحاكاة العلاقة التراجعية مباشرة انطلاقًا من \(d_0=0\) وقيمة تجريبية \(d_1=x\). وفي كل خطوة تُفحَص الفجوة \(d_k-d_{k-1}\)، فإذا أصبحت غير موجبة يُرفض ذلك المرشح فورًا.
وللعثور على الفرع المقبول العلوي، تبدأ التطبيقات بمسح خشن على المجال \(0.6\le x\le 1.5\) بخطوة \(0.01\). وبهذا يُكتشَف أول انتقال من الفشل إلى النجاح على ذلك الفرع.
بعد ذلك تُجرى \(90\) خطوة من البحث الثنائي. وتُختبَر نقطة المنتصف في كل مرة بالمحاكاة نفسها، لذلك تنكمش حدود الحافة إلى أن نصل إلى الدقة العائمة المطلوبة.
وبعد تحديد الحافة، يُعاد تشغيل المسار نفسه لتجميع الكلفة. ويتوقف الجمع عندما يتجاوز العمق \(80\)، لأن ما تبقى من الذيل يكون أصغر بكثير من الدقة المعروضة.
أما نسخة C++ فتضيف اختبارات اتساق إضافية قرب الحافة وتقارن مع نقاط مأخوذة من الفرع السفلي، بينما تكتفي نسختا Python وJava بلبّ عملية البحث والتقييم.
لنرمز بـ \(T\) إلى العدد الأقصى لخطوات العلاقة التراجعية في محاكاة واحدة. هنا \(T\le 200\). وعليه فإن اختبار القبول مرة واحدة أو حساب الكلفة مرة واحدة يحتاج إلى زمن \(O(T)\) وذاكرة \(O(1)\).
إذا استُخدمت \(S\) نقاط في المسح الخشن و\(B\) خطوات في البحث الثنائي، فإن الزمن الكلي يساوي
$$O((S+B)T).$$
وبما أن \(B=O(\log(1/\varepsilon))\) عندما تكون \(\varepsilon\) هي الدقة المطلوبة، فيمكن أيضًا كتابة ذلك على صورة \(O(T\log(1/\varepsilon))\) بعد تثبيت مجال المسح الأولي. ولأن جميع الثوابت صغيرة وثابتة في التطبيقات، فإن زمن التنفيذ العملي يكون ثابتًا تقريبًا، بينما تبقى الذاكرة \(O(1)\).