Какова временная сложность троичного поиска при применении к двойникам?

avatar
Ziad El-Gafy
8 августа 2021 в 18:52
76
1
4

Я знаю, что временная сложность обычного троичного поиска составляет O(log3 n), но что, если он используется с числами с плавающей запятой?

Пример: какова временная сложность этого блока этого блока кода?

double s = -100, m1, m2, e = 100, EPS = 1e-6; 
while(abs(s-e) > EPS)
{     
    m1 = s + (e - s) / 3;
    m2 = e - (e - s) / 3;

    if(condition)
        e = m2;
    else
        s = m1;
}

Все, что он делает, это ищет действительное число между -100 и 100, но временная сложность изменяется, когда изменяется точность переменной EPS.

Источник
Matt Timmermans
9 августа 2021 в 11:55
1

Примечание. Log_3(n) = log(n)/log(3) — в O(log n) основание не имеет значения.

Ответы (1)

avatar
Codie CodeMonkey
8 августа 2021 в 23:53
3

Сложность O(log 3(e-s)/EPS). Мы можем свести задачу к целочисленному случаю, где n=ceil((e-s)/ESP). (Здесь ceil(x) — это функция, которая отображает x в следующее целое число j, такое что x <= j < x+1.)

Пусть delta = (e-s)/n <= EPS. Легко убедиться, что delta <= EPS. На i-м шаге алгоритма либо s[i], либо e[i] были перемещены из своего предшественника (s[i-1] или e[i-1]) в другой интервал I[i], заданный <83917978,289 или иначе s[i]> и e[i] находятся в пределах delta друг от друга, и в этом случае они находятся в пределах EPS друг от друга.