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

[Anonymous]

Примечание. Это мой первый вопрос о переполнении стека, поэтому я ценю любые рекомендации по улучшению моего вопроса или предоставленной информации.
Я реализовал функцию Python для вычисления числа Пи с помощью метод двоичного разделения, и мне любопытно, верен ли мой анализ его временной сложности. Вот реализация:

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

from collections import deque
from math import sqrt

def pi(n = 5000):
if not isinstance(n, int):
raise TypeError(f"'{type(n).__name__}' object cannot be interpreted as an int.")
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 = 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 = sqrt(10005) * 426880
P, Q, R = pi_binary_split_iter(n)
return (C * Q) / (13591409 * Q + R)

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

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