Расчет временной сложности этого алгоритма

Question

Я пытаюсь вычислить временную сложность этого алгоритма, который определяет, можно ли выразить положительное целое число N как x^y. Автор алгоритма Vaibhav Gupta.

// Returns true if n can be written as x^y 
bool isPower(unsigned int n) 
{ 
    // Base case 
    if (n <= 1) return true; 

    // Try all numbers from 2 to sqrt(n) as base 
    for (int x=2; x<=sqrt(n); x++) 
    { 
     unsigned p = x; 

     // Keep multiplying p with x while is smaller 
     // than or equal to x 
     while (p <= n) 
     { 
      p *= x; 
      if (p == n) 
       return true; 
     } 
    } 
    return false; 
} 

Автор говорит, что этот алгоритм является оптимизированной версией первого, которая:

// Returns true if n can be written as x^y 
bool isPower(unsigned n) 
{ 
    if (n==1) return true; 

    // Try all numbers from 2 to sqrt(n) as base 
    for (int x=2; x<=sqrt(n); x++) 
    { 
     unsigned y = 2; 
     unsigned p = pow(x, y); 

     // Keep increasing y while power 'p' is smaller 
     // than n. 
     while (p<=n && p>0) 
     { 
      if (p==n) 
       return true; 
      y++; 
      p = pow(x, y); 
     } 
    } 
    return false; 
} 

ли это первый из них имеет различные сложности времени, так как он использует функцию POW?

Answer 1

кажется мне, как внешний контур квадратный корень из п, а внутренние петли в порядке лог п (так как число растет экспоненциально), поэтому ваша сложность должна быть что-то в размере

O(sqrt(n)*log n) 

Answer 2

Когда он возвращает false, алгоритм пытается увеличить степень всех целых чисел x, пока они не превысят n. Поиск останавливается после того, как x = √n был опробован.

Так что для грубой оценки, не оценивая полномочия до x^d = n занимает около log n/log x размножается, и повторяется из x=2 в x=√n.

Поэтому сложность подобна

log n.Sum(x=2 to √n)1/log x 

, который непросто оценить, но O(log n.√n) и Ω(√n).

pow версия принимает log d умножает вместо 1, чтобы вычислить мощность, при условии, что она делает это путем повторных квадратур. Как d = log n/log x, сложность, как

log n.Sum(x=2 to √n)(log log n - log log x)/log x 

еще сложнее оценить, но и O(log n.log log n.√n)Ω(√n).

Для диапазона n, охватываемого типом int, вы можете ожидать, что версия pow будет находиться в пределах от одного до пяти раз медленнее (если функция pow не имеет больших накладных расходов).