вычислить сложность времени алгоритма квадратного корня

Question

Я проходил ниже ссылку enter link description here и через ответы Я хотел рассчитать сложность времени ниже предлагаемого кода. Я играл с довольно многими значениями, и количество шагов колеблется между 23 (даже для небольших значений) и говорит 50 для реальных больших значений. Как мне рассчитать сложность времени для кода ниже - любые указатели?

float val, low, high, mid, oldmid, midsqr; 
// Set initial bounds and print heading. 
low = 0; high = mid = val; oldmid = -1; 

// Keep going until accurate enough. 
while (fabs(oldmid - mid) >= 0.00001) 
{ 
    oldmid = mid; 
    // Get midpoint and see if we need lower or higher. 
    mid = (high + low)/2; 
    midsqr = mid * mid; 
    if (mid * mid > val) 
    { 
     high = mid; 
     printf("- too high\n"); 
    } 
    else 
    { 
     low = mid; 
     printf("- too low\n"); 
    } 
} 

Answer 1

С точки зрения определения временной сложности, подумайте о том, сколько «шагов» вашего алгоритма предпримет для прекращения.

В этом случае мы, по сути, бинарный поиск, чтобы найти квадратный корень. Таким образом, количество шагов, которые нам нужно учитывать, - это то, сколько сравнений вы делаете. Поскольку это бинарный поиск, мы знаем, что он находится в области O(log(n)), так как вы можете думать о бинарном поиске как о сокращении наполовину пространства для поиска каждый раз.

Итак, теперь нам нужно выяснить, что такое n. Мы ищем диапазон (low, high), который находится от (0, val). Но поскольку мы ищем поплавки, а точность, о которой вы заботитесь, составляет до 0.00001, мы можем эффективно умножить диапазон на 100000, чтобы мы могли подумать о проблеме на ints.

Тогда у нас будет временная сложность O(log(100000 * val)), которая находится в O(log(val)) (если точность не постоянна).

Answer 2

Вы должны признать алгоритм, который вы представляете в виде двоичного поиска. Поскольку вы впервые провели анализ сложности, я полагаю, вы знаете, что сложность двоичного поиска - O(log N).

Основным потенциальным осложнением является вопрос о том, что касается N. Возможно, у вас возникнет соблазн подумать, что это значение, квадратный корень которого вы пытаетесь определить (т. Е. Квадрат), но это будет примерно правильно. Скорее, это число различных точек в пространстве поиска. Это зависит от границ поискового пространства, и ваш критерий для чисел внутри него должен быть различным (в этом случае они отличаются более чем на 0.00001).

Поскольку представимые числа с плавающей запятой неравномерно распределены, это не так просто, как (upper_bound - lower_bound)/0.00001, но вы можете принять это в грубом приближении. Если, кроме того, вы используете 0 как нижнюю границу и фиксированное кратное (возможно, 1) квадрата в качестве верхней границы, то это приближение дает вам O(log square) как общую сложность.

Рассмотрим теперь, что, поскольку алгоритм масштабируется логарифмически, удвоение размера пространства поиска приводит к фиксированному приращению максимального количества шагов в поиске. Поскольку это конкретный бинарный поиск, разница в 27 шагов между одним прогоном и другим должна соответствовать коэффициенту около 2 (примерно 127 000 000) в размере пространства поиска.