A while l oop временная сложность

Question

Мне интересно определить большую временную сложность O следующего:

def f(x):
    r = x / 2
    d = 1e-10
    while abs(x - r**2) > d:
        r = (r + x/r) / 2
    return r

Я считаю, что это O (log n). Чтобы прийти к этому, я просто собрал эмпирические данные с помощью модуля timeit и построил результаты, и увидел, что график, который выглядел логарифмически c с использованием следующего кода:

ns = np.linspace(1, 50_000, 100, dtype=int)
ts = [timeit.timeit('f({})'.format(n), 
                    number=100, 
                    globals=globals()) 
      for n in ns]
plt.plot(ns, ts, 'or')

Но это похоже на банальный способ go выяснить это. Интуитивно я понимаю, что тело while l oop включает в себя деление выражения на 2 некоторое число k раз, пока выражение while не станет равно d. Это повторное деление на 2 дает что-то вроде 1/2 ^ k, из которого я могу видеть, где используется журнал для решения для k. Однако я не могу описать более явный вывод. Любая помощь?

Answer 1

Это метод Герона (или вавилонского) для вычисления root квадрата числа. https://en.wikipedia.org/wiki/Methods_of_computing_square_roots

Нотация Big O для этого требует подхода численного анализа. Для получения дополнительной информации об анализе вы можете проверить указанную страницу википедии или найти сходимость ошибок Heron или итерацию с фиксированной точкой. (или посмотрите здесь https://mathcirclesofchicago.org/wp-content/uploads/2015/08/johnson.pdf)

В общих чертах, если мы можем записать ошибку e_n = (x-r_n**2) в терминах самой себя, где e_n = (e_n**2)/(2*(e_n+1))

Тогда мы можно увидеть, что e_n+1 <= min{(e_n**2)/2,e_n/2}, поэтому ошибка уменьшается квадратично. Со степенями точности, эффективно удваивающими каждую итерацию.

Отличие этого анализа от Big-O заключается в том, что время, которое он занимает, НЕ зависит от размера входных данных, а зависит от желаемой точности. Таким образом, с точки зрения ввода, это, в то время как l oop равно O (1), потому что его количество итераций ограничено точностью, а не вводом.

С точки зрения точности ошибка ограничена указанным выше значением e_n < 2**(-n), поэтому нам нужно найти -n такое, что 2**(-n) < d. Итак, log_2(d) = b такое, что 2^b = d. Предполагая, что d <2, тогда <code>n = floor(log_2(d)) будет работать. Итак, с точки зрения d, это O (log (d)).

EDIT: Дополнительная информация об анализе ошибок итерации с фиксированной точкой http://www.maths.lth.se/na/courses/FMN050/media/material/part3_1.pdf

Answer 2

Я считаю, что вы правы, что это O (log n).

Здесь вы можете увидеть последовательные значения r, когда x = 100000:

1 50000
2 25001
3 12502
4 6255
5 3136
6 1584
7 823
8 472
9 342
10 317
11 316
12 316

(I округлили их, потому что дроби не интересны).

Что вы можете увидеть, если оно проходит через две фазы.

Фаза 1 - это когда r велико. Во время этих первых нескольких итераций x/r крошечный по сравнению с r. В результате r + x/r близко к r, поэтому (r + x/r) / 2 примерно равно r/2. Вы можете увидеть это на первых 8 итерациях.

Фаза 2 - это когда он приближается к окончательному результату. Во время последних нескольких итераций x/r близко к r, поэтому r + x/r близко к 2 * r, поэтому (r + x/r) / 2 близко к r. На данный момент мы просто немного улучшаем приближение. Эти итерации на самом деле не очень сильно зависят от величины x.

Вот последовательность для x = 1000000 (в 10 раз больше):

1 500000
2 250001
3 125002
4 62505
5 31261
6 15646
7 7855
8 3991
9 2121
10 1296
11 1034
12 1001
13 1000
14 1000

На этот раз в Фазе 1 10 итераций, затем мы снова имеем 4 итерации во Фазе 2.

В сложности алгоритма преобладает Фаза 1, которая является логарифмической c, потому что каждый раз она приблизительно делится на 2.