このアルゴリズムの時間計算量を計算する

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; 
} 

著者は、このアルゴリズムは最初の1の最適化バージョンであることを言う：

// 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; 
} 

んこの最初の一つは、彼が捕虜機能を使用していますので、異なる時間の複雑さを持っていますか？外側のループは、nの平方根であるよう

Answer 1

は私に見える、と（数は指数関数的に増加するので）、内側のループは、ログ、nの順になっているので、あなたの複雑さが

O(sqrt(n)*log n) 

の曲で何かする必要があります

Answer 2

falseを返すと、アルゴリズムはを超えるまで、すべての整数の累乗を増加しようとします。xx = √nが試行された後、検索が停止します。

だからラフな評価のために、 x^d = nまで力を評価することについて log n/log x乗算を取り、 x=√nに x=2から繰り返されます。

したがって複雑さが

推定する不安である

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

が、O(log n.√n)とΩ(√n)ようなものです。

powバージョンは、電力を計算するために1の代わりにlog dの乗算を使用します（ただし、繰り返されるスクエア化によって得られます）。 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のバージョンが1倍から5倍遅くなることが予想されます。