Berechnen der Zeitkomplexität dieses Algorithmus

Question

Ich versuche, die Zeitkomplexität dieses Algorithmus zu berechnen, der bestimmt, ob eine positive Ganzzahl N als x^y ausgedrückt werden kann. Der Autor des Algorithmus ist 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; 
} 

Der Autor sagt, dass dieser Algorithmus ist eine optimierte Version des ersten, das ist:

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

Ist diese erste eine andere Zeitkomplexität hat, seit er die pow-Funktion verwendet?

Answer 1

mir Sieht aus wie die äußere Schleife Quadratwurzel von n ist und die inneren Schleifen sind in der Größenordnung von log n (da die Zahl wächst exponentiell) so Ihre Komplexität sollte etwas in der Größenordnung von

O(sqrt(n)*log n) 

sein

Answer 2

Wenn false zurückgegeben wird, versucht der Algorithmus, die Potenzen aller Ganzzahlen x zu erhöhen, bis sie n überschreiten. Die Suche wird beendet, nachdem x = √n ausprobiert wurde.

Also für eine grobe Auswertung, nimmt die Befugnisse bis x^d = n Auswertung über log n/log x vervielfacht und x=2-x=√n wiederholt.

Daraus ergibt sich die Komplexität ist wie

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

, die zu schätzen unbehaglich, sondern O(log n.√n) und Ω(√n).

Die pow Version nimmt log d multipliziert statt 1, um eine Leistung zu berechnen, vorausgesetzt es geschieht durch wiederholte Quadrierungen. Wie d = log n/log x ist die Komplexität wie

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

noch schwerer zu schätzen, aber O(log n.log log n.√n) und Ω(√n).

Für den Bereich von n vom Typ int bedeckt, können Sie die pow Version zwischen einmal und fünfmal langsamer (es sei denn, die pow Funktion hat einen großen Overhead) erwarten.