Как оценить сложность алгоритма не зная кол-во итераций

Question

Есть алгоритм

cin >> e;
int n = 1;
double S = 0, i = 0;

do
{
    S += i;
    i = 1 / (pow(3, n) - 1);
    n++;
} while (i >= e);

cout << "Сумма S = " << S;

он же на изображении

По заданию необходимо определить оценку его сложности. Мне не понятно как это делать, т.к. у нас нет заранее известного количества элементов и т.д., и мы выполняем цикл пока очередной элемент не будет меньше точности.

По методичке алгоритм такой:

посчитать в лучшем случае - тут понятно, чтобы первый рассчитанный элемент был меньше точности.
посчитать в худшем случае - тут у меня проблемы. Была идея посчитать основываясь на том, что точность (Е) будет минимальной (по стандарту IEEE 754 для числа с плавающей точкой -1,17549435∙e-38), а первый рассчитанный элемент в сумме S будет максимальным, и двигаться к точности E очень медленно. Я думаю это корректно, но это сложно формализовать, возможно есть ответ проще.

Answer 1

Почему же это у нас нет заранее известного количества элементов?

Мы вполне можем вывести n из заданной точности e (здесь и далее e - это не число Эйлера, а точность из условия вопроса), составив элементарное уравнение e=1/(3^n-1) и решая его относительно n, решением которого будет n=log(1+1/e)/log(3), где log - натуральный логарифм, хотя на оценку сложности это не влияет.

То есть очевидно у нас будет не менее log(1+1/e)/log(3) итераций, дальнейший расчёт временной сложности алгоритма зависит от того как мы считаем 3^n. Обычно линейно в степень никто не возводит, а используют алгоритмы быстрого возведения в степень, где сложность = log(n), хотя скорее всего в большинстве реализаций std::pow будет выполняться за О(1), тут можно прочитать чуть подробнее: https://stackoverflow.com/questions/13418180/time-complexity-of-c-math-library-pow-function

Таким образом получаем сложность нашего алгоритма вычисления суммы = O(N*временная сложность pow), где N = log(1+1/e)/log(3).

В случае если std::pow выполняется за константное время, получаем O(log(1+1/e))

БЛОГ НА HUSL

Как оценить сложность алгоритма не зная кол-во итераций

Ответы (1 шт):