6
votes

Complexité de temps Java O (n ^ 2/3)

Mon arrière-plan mathématique n'est pas si bon, c'est ma tentative d'écrire le code Java avec une proportion d'exécution à une entrée différente.

avec n ^ 2/3. Depuis n ^ 2/3 = racine cube n * cube root n, donc je peux écrire p>

public int fibonnaci(int n) {
    if (n <= 1) {
        return 1;
    } else {
        return fibonnaci(n - 2) + fibonnaci(n - 1);
    }
}

avec 4 ^ n. Puis-je utiliser la méthode FIBonnaci? P>

public void test(int n){
    for (int i = 0; i*i*i < n; i++) {
        for (int j = 0; j*j*j < n; j++) {
            count ++;
        }
    }
}

java algorithm time-complexity big-o

1 commentaires

2) Fibonacci - C'est plus O (2 ^ N) ISO O (N ^ 4). Utilisez 4 personnes nichées pour des boucles (qui sont passées de 1 à N incrémentées de 1) comme exemple de O (n ^ 4) ;-) et 1) est un exemple intelligent :)

3 Réponses :

1
votes

Vous écrivez simplement n'importe quel code qui prend du temps-complexité de cette Big-O Lié?

que pour # 1, oui, il faudrait o (n ^ (2/3)) .

mais pour # 2, votre code prendrait O (2 ^ n) et theta (1.6 ... ^ n) et 1.6 .. est le Numéro de ratio doré célèbre.

Référence: Complexité de calcul de la séquence Fibonacci



                                                                    
                                    
                                    
                                        0 commentaires


                        
                                            
                            
                                
                                    5
 votes
                                
                            
                            
                                
                                      Le premier est correct  fort>, et vraiment bien pensé. 
   le second n'est pas  fort>. Cet algorithme de calcul de la FIBS a une complexité de temps beaucoup plus élevée que O (n ^ 4) ( edit  strong>:  qui a été demandé quand j'ai écrit cette réponse - la question a été mise à jour par-dessus? / em>). Ce n'est même pas polnomial. Le raisonnement est le suivant (notation #fib (x): Nombre de fois FIB est appelé à calculer FIB (x)):  P> 

 fib (1): #fib (1) = 1 (il renvoie directement le résultat)  li>
 FIB (2): #fib (2) = 3 (un pour FIB (2), qui l'appelle pour FIB (0) et FIB (1))  LI>
 FIB (3): #fib (3) = 5 (un pour FIB (3), qui l'appelle pour FIB (2) et FIB (1), donnant 3 + 1 d'autres appels)  LI>
 FIB (4): #fib (4) = 9  LI>
 FIB (5): #fib (5) = 15  LI>
 FIB (6): #fib (6) = 25  LI>
 ...  li>
 fib (i): #fib (i) = 1 + #fib (I-1) + #fib (I-2)  Li>
 ul>  Donc, vous avez:  p> 

 #fib (i) ~ = # #fib (I-1) + #fib (I-2)  Li>
 ul>  De cela, ce serait une supposition raisonnable que le calcul de la FIB (i) prend "environ" (en fait, un peu moins de) 2 fois le temps de calculer FIB (I-1). Par conséquent, vous pourriez "deviner" que o (#fib (i)) = O (2 ^ i). C'est la bonne réponse, que vous pouvez prouver facilement par induction.  P> 
 Juste pour terminer sur la séquence Fibonacci, il y a beaucoup d'algorithmes plus rapides pour calculer le N-ème numéro. Par exemple, un algorithme avec du temps linéaire (IE, O (N)) est de mémoiser cette fonction que vous avez écrite (c'est-à-dire que vous pouvez consulter une carte pour vérifier si elle connaît le résultat pour N, est donc ainsi de retourner immédiatement, sinon, calculez Il le stocke et le retourner). Il y a aussi un   Formule fermée pour calculer la n-e fib   fort>, donc un algorithme de temps constant (c'est-à-dire O (1)).  P> 
  enfin,  Un exemple de O (n ^ 4)  fort> algorithme est quelque chose avec 4 boucles intérieures, chaque boucle en marche "à propos de" n fois.  P> 
 Par exemple, calculez le volume de n cubes de côté N (de manière non optimale):  P> 
int volume = 0;
for (int cube = 0; cube < n; cube++)
  for (int x = 0; x < n; x++)
    for (int y = 0; y < n; y++)
      for (int z = 0; z < n; z++)
        volume++;
return volume;

                                

                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    @Louiswasserman, bien noté. Cependant, lorsque j'ai répondu à la question, on m'a posé une question sur N ^ 4, l'OP l'a changé plus tard, après avoir écrit cela. Désolé pour le dérangement.                                                
                                                
                                                                                    
                                    
                                                            
                        
                        
                                            
                            
                                
                                    1
 votes
                                
                            
                            
                                
                                     Ce n'est pas vraiment une réponse, mais voici un croquis d'une solution "triche" au problème de la fourniture d'un exemple de programme qui prend  O (f (n))  code> temps; 
  Créez un objet de fonction Java pour évaluer  f (n)  code> pour un  n  code>:  p>  li>
  transmettez-le comme paramètre sur la méthode suivante:  p>  li>
 OL> 
    public void computeOrderFN(int n, FunctionInt2Int fn) {
      int count = fn.evaluate(n);
      for (int i = 1; i < count; i++) {
          // Do something O(1) that the compiler can't optimize away)
      }
   }

                                

                                                                    
                                    
                                    
                                        0 commentaires