Каким образом оценивать сложность алгоритма в нотации О-больше?

#алгоритм #javascript

Алгоритм поиска корня числа num. В алгоритме также используется sqrt, это приблизительный
корень.
function getsqrt (num, sqrt) {
  sqrt = 0.5*(sqrt+num/sqrt);
  var sqrtPrev = sqrt;
  while (Math.abs(sqrt-sqrtPrev) <= (sqrt-sqrtPrev)) {
    sqrtPrev = sqrt;
    sqrt = 0.5*(sqrt+num/sqrt);
  }
  return sqrt;
}

Какова сложность алгоритма? Линейная? Логарифмическая и т.д? Меня смущает просто
деления на 2. Мне кажется, это линейная O(n)или логарифмическая.
Обновление

Мои рассуждения следующие: мы имеем один цикл, значит степень первая. Но я не уверен,
что это линейная типа O(n). Потому что в задании есть 0.5*(sqrt+num/sqrt). Соответственно
мне кажется, что это ускоряет поиск корня, нежели мы бы делили просто на 2 или методом
перебора. Прав ли я, что это логарифмическая зависимость по основанию 2?    

Ответы

Ответ 1

Для Вашей функции сложно судить, какая у нее сложность - у Вас два аргумента. Поэтому,
нужно либо фиксировать один аргумент, либо вводить зависимость между ними.
Я использовал простое - sqrt = num/2. и пошел по самому простому пути - тестил на
разных значениях аргумента и построить график (это один из способов узнать сложность).
Мое мнение - сложность константная (или очень близка к ней).
num  десятые микросекунды (10^-7)
1 -> 32
2 -> 27
4 -> 24
8 -> 24
16 -> 23
32 -> 23
64 -> 23
128 -> 26
256 -> 24
512 -> 23
1024 -> 23
2048 -> 24
4096 -> 23
8192 -> 23
16384 -> 23
32768 -> 22
65536 -> 23
131072 -> 24
262144 -> 23
524288 -> 23
1048576 -> 24
2097152 -> 23
4194304 -> 24
8388608 -> 23
16777216 -> 23
33554432 -> 24
67108864 -> 23
134217728 -> 23
268435456 -> 24
536870912 -> 24

Как видно на первых проходах идет "прогрев" (это отрабатывает jit компилятор).
Кстати, в Вашем коде есть одна ошибка - он иногда зависает. И зависает, если попытаться
извлечь корень из числа, для которого он рациональный. (как минимум зависает на 4 и 10000).
полный код для тестов и исправление (все тестилось на node.js).
function getsqrt (num, sqrt) {
  sqrt = 0.5*(sqrt+num/sqrt);
  var sqrtPrev = sqrt;
  while (Math.abs(sqrt-sqrtPrev) < (sqrt-sqrtPrev)) {
    sqrtPrev = sqrt;
    sqrt = 0.5*(sqrt+num/sqrt);
  }
  return sqrt;
}

function test(num)
{
    var start = new Date();
    for (var i = 0; i < 10000000; i++) {
        getsqrt(num, num / 2);
    }
    var end = new Date();
    return end.setTime(end.getTime()-start.getTime())
}

for (var i = 1; i < 1000000000; i = i*2) {
  console.log(i + " -> " + test(i));
}

P.S. В тегах указано с++, а код написан на JavaScript. Поэтому свой код я написал
также на JavaScript.
Обновление
я разобрался, почему она константа. Потому что цикл обычно выполняется 1 раз или
0 (так у меня получается). Присмотритесь к условию
while (Math.abs(sqrt-sqrtPrev) <= (sqrt-sqrtPrev))

sqrt-sqrtPrev используется в обеих частях! А если вспомните, то есть такое правило
- не сравнивать на равенство вещественные числа (на больше-меньше можно, но осторожно,
если числа близкие).
Если там равно, то оно сработает только в том случае, если sqrt-sqrtPrev > 0 и немного
повезет (на самом деле, если разница представима конечной двоичной дробью).
Поэтому, сложность у алгоритма константная:).


Ответ 2

Если чуть-чуть изменить приведенный фрагмент программы следующим образом:
function getsqrt (num, sqrt) {
  var sqrtPrev = sqrt;
  sqrt = 0.5*(sqrt+num/sqrt);
  while (Math.abs(sqrt-sqrtPrev) > 1e-5) {
    sqrtPrev = sqrt;
    sqrt = 0.5*(sqrt+num/sqrt);
  }
  return sqrt;
}

То получившаяся программа будет реализацией известного метода Ньютона для отыскания
корня уравнения x^2 - num = 0.
Про метод Ньютона известно, что (в некоторой окрестности решения) он обладает квадратичной
сходимостью. Это означает, что на каждом следующем шаге значение невязки diff, то есть
разности между значением sqrt и квадратным корнем из num, меньше, чем квадрат невязки,
вычисленной на предыдущем шаге.
Число итераций цикла зависит как от величины числа num, так и от величины требуемой
точности. В примере эта величина фиксирована: 1e-5, но допустим, что она также может
меняться. Обозначим требуемую точность именем eps. Тогда для метода Ньютона можно дать
оценку числа итераций O(log log (num/eps)).