0
votes

Est-ce qu'une fonction Big-o elle-même?

Tout en travaillant à travers un cours de base dans la notation asymptotique, je suis arrivé à un ensemble de problèmes dans lesquels je suis censé trouver une fonction (g (n)) de telle qu'une fonction donnée F (n) = O (g (n). ))). Après avoir travaillé par ces problèmes un peu je suis venu me demander; Toutes les fonctions ne sont-elles pas big-o d'eux-mêmes? Ils seront éventuellement liés par certains C * F (N) DONNER F (N) est la fonction d'origine. J'ai essayé de prouver cela incorrect dans Desmos en vain.

suis-je fondamentalement mal compris la notation Big-O? Le but est-il davantage de prouver que certains algorithmes ont définitivement moins de temps d'exécution, puis d'autres plutôt que de les être liés avec une fonction arbitraire? Toute clarification est très appréciée. Merci.

algorithm big-o

0 commentaires

4 Réponses :

2
votes

Vous pouvez trouver des ressources sur toutes les notations autour de la zone ici .

théoriquement oui, toute fonction est une grosse O de lui-même. C'est mathématiquement une tautologie. Mais à partir de ma compréhension, Big-O est généralement utilisé pour convertir une relation complexe de la taille de l'exécution de la taille d'entrée dans une estimation simple et élégante du comportement asymptotique pour de grandes tailles d'entrée. Habituellement, nous gardons uniquement les termes les plus importants et omettent les autres et les constantes. Puisque pour le grand n, seuls les termes les plus significatifs se distinguent.

E.g. Vous avez deux solutions à un problème, un coût t1 (n) = n ^ 2 + 100 * N + 30 * log (n) , les autres coûts T2 (n) = 10000n + 40 * sqrt (n) . Utilisation de la notation Big-O, nous savons que t1 (n) est o (n ^ 2) et t2 (n) est O (n) , donc pour les grandes entrées, la méthode 2 pourrait être plus souhaitable car elle pousse asymptotiquement linéairement avec n.



                                                                    
                                    
                                    
                                        0 commentaires


                        
                                            
                            
                                
                                    2
 votes
                                
                            
                            
                                
                                     Vous pouvez le prouver par la définition du Big-o. En tant que  lim f (n) / f (n)  lorsque  n  va sur  \ \ \ \ great  est égal à  1  et constante, nous pouvons dire  f (n) = \ theta (f (n)) , et cela signifie  f (n) = O (f (n))  et < Code> f (n) = \ oméga (f (n)) .                                 


                                                                    
                                    
                                    
                                        1 commentaires
                                        
                                                                                            
                                                    C'est ce que je pensais, merci pour la preuve aide à mettre des choses en perspective quantitative                                                
                                                
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                    
   am je suis fondamentalement mal compris la notation Big-O? 


 Je crains que vous soyez parce que la question  "est une fonction Big-o elle-même?"  sonne bizarre pour moi. 


   est le but davantage de prouver que certains algorithmes ont définitivement
  plus petit temps d'exécution puis d'autres plutôt que de les être liés avec un arbitraire
  fonctionner? 


 absolument. 

 Rappelez-vous que Big-O est une notation mathématique. Il est largement utilisé pour simplifier l'écriture d'une formule. Par exemple, une série de tyror expansion d'une fonction F (x) où nous ne voulons pas écrire la formule exacte de l'erreur d'approximation, mais je veux toujours savoir - en lisant la formule - que cette erreur se comporte comme une fonction polynomiale lorsque x tend à infini ou vers une valeur spécifique. 

 Mais la plupart du temps, nous sommes généralement intéressés par le coût dans le temps et dans l'espace d'une fonction (au sens de programmation) et nous souhaitons comparer l'efficacité de 2 algorithmes lorsque l'ensemble de données est grand. 

 C'est là que la notation Big-O est utile: nous savons que nous pouvons comparer le coût de l'algorithme A et B en comparant leurs homologues Big-O - c'est-à-dire leur complexité des coûts exprimée en polynôme, constante ou la fonction logarithmique (ou tout ce qui est plus facile à comparer) d'une variable N, où N est la taille de l'ensemble de données (taille d'un tableau, nombre d'éléments dans un ensemble ...)                                 


                                                                    
                                    
                                    
                                        0 commentaires
                                        
                                                                                    
                                    
                                                            

                        

                        
                                            
                            
                                
                                    0
 votes
                                
                            
                            
                                
                                     Les réponses données ci-dessus sont superbes, mais voici un ajout qui rendrait cette page de questions complète. Je suppose que vous avez lu le lien dans la réponse ci-dessus et connaissez la notation Big-O, Theta et Omega. 

 Je suppose que ce que vous demandez est: y a-t-il un  f (n)  tel que  f (n) = O (f (n)) ? 

 Peut-être. Mais il existe de nombreux cas où où  f (n) = θ (f (n)) . Cela se produit lorsque  f (n) = t (f (n))  c'est-à-dire une fonction qui entrait un entier et des sorties un entier est défini de la même manière que la fonction temporelle. 

 Ceci est particulièrement vrai de la fonction de la série Fibonacci. J'ai commencé à taper une preuve, mais je vais différer en faveur de cette réponse:  https://stackoverflow.com/a/360773/11252937 < / a> 

 Si le lien tombe en panne, voici un extrait: 


   Vous modélisez la fonction de temps pour calculer FIB (N) comme une somme de temps pour calculer FIB (N-1) plus le temps nécessaire pour calculer FIB (N-2) plus le temps nécessaire pour les ajouter ensemble (O (1)) . Cela suppose que les évaluations répétées du même fib (n) prennent la même heure - c'est-à-dire. Aucune mémoisation n'est utilisée. 
  
  
 t (n <= 1) = O (1) 
  
  
 t (n) = t (n-1) + t (n-2) + O (1) 
  
  
 Vous résolvez cette relation de récurrence (en utilisant des fonctions génératrices, par exemple) et vous vous retrouverez avec la réponse. 
  
  
 Alternativement, vous pouvez dessiner l'arborescence de la récursivité, qui aura une profondeur N et déterminera intuitivement que cette fonction est asymptotiquement O (2 ^ N). Vous pouvez ensuite prouver votre conjecture par induction. 
  
  
 base: n = 1 est évident 
  
  
 suppose t (n-1) = O (2 ^ (n-1)), donc 
  
  
 t (n) = t (n-1) + T (n-2) + O (1) égal à 
  
  
 t (n) = O (2 ^ (N-1)) + O (2 ^ (N-2)) + O (1) = O (2 ^ N) 
  
  
 Cependant, comme indiqué dans un commentaire, ce n'est pas la limite serrée. Un fait intéressant sur cette fonction est que le T (N) est asymptotiquement la même chose que la valeur de FIB (N) car les deux sont définies comme 
  
  
 f (n) = f (n-1) + f (n-2). 
  
  
 Les feuilles de l'arborescence de la récursivité seront toujours renvoyées 1. La valeur de FIB (N) est la somme de toutes les valeurs renvoyées par les feuilles dans l'arborescence de la récursivité, ce qui est égal au nombre de feuilles. Étant donné que chaque feuille prendra O (1) pour calculer, t (n) est égale à la fib (n) x O (1). Par conséquent, la limite serrée de cette fonction est la séquence Fibonacci elle-même (~ θ (1,6 ^ N)). Vous pouvez découvrir cette liaison serrée en utilisant des fonctions génératrices comme je l'ai mentionné ci-dessus. 
                                


                                                                    
                                    
                                    
                                        0 commentaires

Articles qui pourrait vous intéresser : Calculer la différence dans l'échelle d'évaluation alphabétique Complexité de Trouver tous les multiples de 3 et 5 entre 1 et 10 000 000 Ma vérification pour savoir si un graphique est un arbre binaire renvoie toujours faux Comment trouver le nombre d'itérations de l'algorithme de recherche binaire?