Какова временная сложность цикла for (связана с `n`)?

Question

Какова временная сложность цикла for (связана с n)?

for(int i = 1, j; i <= n; i = j + 1)
{
        j = n / (n / i);
}

Обратите внимание, что i, j и n являются целочисленными переменными, и они следуют целочисленной арифметике. В частности, выражение n/(n/i) внутри цикла следует интерпретировать следующим образом:

Answer 1

Поскольку @Walter уже предложил доказательство, я опоздал на эту часть, но вот версия вашего кода на Python3 и график количества итераций как функции n против функции 2*sqrt(n) , Они выглядят примерно одинаково (до n = 1e9).

import matplotlib.pyplot as plt
from numba import jit
import math

@jit
def weird_increment_loop(n):
    i = 1
    j = 0
    iterations = 0
    while i <= n:
        j = n // (n // i)
        i = j + 1
        iterations = iterations + 1

    return iterations

iterations = []
func_2sqrt = []
domain = range(0,1000000001,1000000)
for n in domain:
    iterations.append(weird_increment_loop(n))
    func_2sqrt.append(math.sqrt(n)*2)

plt.plot(domain,iterations)
plt.plot(domain,func_2sqrt)
plt.xlabel("n")
plt.ylabel("iterations(n) and 2*sqrt(n)")
plt.show()

Вот сюжет:

Если вы не видите никакой разницы, то это потому, что их почти нет: D Конечно, всегда следует доверять математике;)

Answer 2

Строго по правилам C ++, это O(1). Либо цикл завершается после некоторого конечного количества выполнения не наблюдаемой работы, либо он зацикливается навсегда (что является неопределенным поведением). Соответствующая реализация может предполагать, что неопределенное поведение не встречается, поэтому мы можем предположить, что оно заканчивается.

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

Answer 3

Поскольку разработано Таотси , приращение для i в каждой итерации составляет

inc = 1 + r/k

, где r=n%i и k=n/i. Начиная с r<i, приращение равно 1 до i<sqrt(n) (потому что тогда i*i/n<1 становится 0 в целочисленном делении). После этого приращение составляет (обычно) 2 до i<2*sqrt(n). Это продолжается аналогично геометрическому ряду, давая коэффициент 2 за sqrt(n), то есть 2 sqrt(n) итераций.

Если мы напишем n = a*a+b с целыми числами 0 <= b <= 2*a (то есть a=int(sqrt(n)) и b=n-a*a), то общее число итераций в простых экспериментах всегда равно

b < a?  2*a-1 : 2*a

Таким образом, сложность составляет O (√n) (при условии, что внутри цикла выполняется некоторая полезная работа, например, подсчет количества полных итераций, так что компилятору не разрешается исключать весь цикл).

Answer 4

Если мы используем j = i; вместо j = n / (n / i);, сложность времени будет O (n). Теперь это j = n / (n / i);, предположим, что n = i * k + r , где k и r - целые числа, а r = n% i . Таким образом, j = (i * k + r) / ((i * k + r) / i) = (i * k + r) / k = i + r / k> = i, что означает, что i будет увеличиваться быстрее, чем случай, когда вы используете j = i;. Так что, по крайней мере, временная сложность меньше, чем O (n), что, я полагаю, дает вам еще один O (n).

И, кроме большой записи O, существуют еще две записи (Θ и Ω), которые означают нижнюю и верхнюю границу O (n). Вы можете получить сложность времени, найдя эти две границы. И есть другое правило, если я правильно помню, O (k * n) = O (n), коэффициент k не имеет значения, независимо от того, насколько он велик.