Достигает ли моя реализация вычисления числа Пи на языке O(n) временной сложности? ⇐ Python

[Anonymous]

Примечание. Это мой первый вопрос о переполнении стека, поэтому я был бы признателен за любые рекомендации по улучшению моего вопроса или предоставленной информации.
РЕДАКТИРОВАТЬ: я немного изменил код, чтобы используйте пакет Decimal для большей точности.
Я реализовал функцию Python для вычисления числа Пи с использованием метода двоичного разделения, и мне интересно, верен ли мой анализ ее временной сложности. Вот реализация:

Код: Выделить всё

from collections import deque
from decimal import Decimal, getcontext

def pi(n=5000, decimal_prec=10000):
getcontext().prec = decimal_prec

if not isinstance(n, int):
raise TypeError(f"'{type(n).__name__}' object cannot be interpreted as an integer")
if n < 2:
raise ValueError("Terms must be more than 1")

def pi_binary_split_iter(n):
distribution_stack = deque([(1, n)])
merge_stack = []
results = {}

for _ in range(2 * n - 3):
a, b = distribution_stack.pop()
if a == b - 1:
Pab = (-6 * a + 5) * (2 * a - 1) * (6 * a - 1)
Qab = Decimal(10939058860032000) * (a ** 3)
Rab = Pab * (545140134 * a + 13591409)
results[(a, b)] = (Pab, Qab, Rab)
else:
m = (a + b) // 2
merge_stack.append((a, b))
distribution_stack.append((a, m))
distribution_stack.append((m, b))

for a, b in reversed(merge_stack):
m = (a + b) // 2
Pam, Qam, Ram = results[(a, m)]
Pmb, Qmb, Rmb = results[(m, b)]
Pab = Pam * Pmb
Qab = Qam * Qmb
Rab = Qmb * Ram + Pam * Rmb
results[(a, b)] = (Pab, Qab, Rab)

return results[(1, n)]

C = Decimal(10005).sqrt() * Decimal(426880)
P, Q, R = pi_binary_split_iter(n)
return (C * Q) / (Decimal(13591409) * Q + R)

Реализация: я реализовал функцию Python для вычисления числа «пи» с использованием алгоритма двоичного разделения.
Анализ сложности: я проанализировал сложность моего алгоритма, в частности сосредоточив внимание на функции pi_binary_split_iter.
Временная сложность: исходя из реализации логики слияния и общей структуры алгоритма, я ожидал, что временная сложность моей функции вычисления числа будет равна O. (n).
Обратная связь: я искал отзывы о том, верен ли мой анализ временной сложности и существуют ли какие-либо потенциальные оптимизации или альтернативные методы, которые могли бы улучшить производительность или точность расчет.
Спасибо.

Подробнее здесь: https://stackoverflow.com/questions/791 ... complexity