Алгоритм поиска корня числа 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?
Ответ
Для Вашей функции сложно судить, какая у нее сложность - у Вас два аргумента. Поэтому, нужно либо фиксировать один аргумент, либо вводить зависимость между ними.
Я использовал простое - 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 и немного повезет (на самом деле, если разница представима конечной двоичной дробью).
Поэтому, сложность у алгоритма константная:).
Комментариев нет:
Отправить комментарий