Big O, quelle est la complexité de l'addition d'une série de n nombres?

J'ai toujours pensé que la complexité de l':

1 + 2 + 3 + ... + n est O(n), et en additionnant les deux n par n matrices serait O(n^2).

Mais aujourd'hui j'ai lu un livre, "la formule de la somme des n premiers nombres entiers, c'est n(n+1)/2" et ensuite ainsi: (1/2)n^2 + (1/2)n, et donc O(n^2).

Ce qui me manque ici?

  • Il serait utile de savoir ce que "cela" est. Vous avez raison, en ajoutant jusqu'à la n des choses (de faire quelque chose de n fois, chacun de coût O(1)) est O(n). Mais si au lieu d'ajouter 1+2+3+ etc vous avez dû faire quelque chose une fois, et puis faire quelque chose deux fois, puis trois fois, etc., puis, après 1+2+3..+n étaient fait vous auriez fait n*(n+1)/2 choses, qui est en O(n^2).
  • Manquant? Bien que vous avez trouvé la formule pour une somme qui l'a expliqué. Quoi d'autre avez-vous besoin d'aide?
  • désolé pour l'ambiguïté, de la "ce" fait référence 1 + 2 + 3 + ... + n
  • donc, juste pour être clair, le "et alors" est votre gloss, pas ce que disait le livre? Parce que si oui, alors je pense que plusieurs des réponses ci-dessous sont correctes et que vous êtes à la confusion de la complexité d'un algorithme de sommation de n nombres en général avec le fait qu'il se trouve que nous pouvons calculer la somme de 1+2+..+n à l'aide d'une formule. Disons que nous avons été sommation de n cases au lieu de cela, 1+4+9+...n^2. La somme de ces (n)(n+1)(2n+1)/6, mais cela ne signifie pas que l'ajout de n des choses ensemble deviendrait O(n^3); il serait plutôt de dire que, dans un cas particulier que nous pourrions obtenir en O(1).
  • Cette lien c'est très utile.
  • Voir aussi math.stackexchange.com/questions/776477/...

InformationsquelleAutor user1032613 | 2012-02-12
  1. 17

    La la notation grand O peut être utilisé pour déterminer le taux de croissance de tout fonction.

    Dans ce cas, il semble que le livre ne parle pas de la complexité du temps de calcul de la valeur, mais sur la valeur elle-même. Et n(n+1)/2 est O(n^2).

    InformationsquelleAutor svick
  2. 8

    Vous confondez la complexité de runtime et de la taille (complexité) de la résultat.

    La temps d'exécution de la sommation, l'un après l'autre, la première n nombres consécutifs est en effet O(n).1

    Mais la complexité de la raison, qui est la taille de la “somme de 1 à n” = n(n – 1) /2 est O(n ^ 2).

    1 Mais arbitrairement grand nombre c'est simpliste puisque l'ajout d'un grand nombre prend plus de temps que l'ajout d'un petit nombre. Pour un précis d'analyse de l'exécution, vous avez en effet tenir compte de la taille du résultat. Cependant, ce n'est pas pertinente en programmation, ni même sur le plan purement théorique de l'informatique. Dans les deux domaines, en additionnant les nombres est généralement considéré comme une O(1) opération, sauf s'il est expressément exigé autrement que par le domaine (c'est à dire lors de la mise en œuvre d'une opération pour un bignum de la bibliothèque).

    • "Le temps d'exécution de la sommation des n premiers nombres consécutifs est, en effet, O(n)" - Non, c'est le temps d'exécution de l'ajout de n des nombres arbitraires. Le temps d'exécution de la sommation des n premiers nombres consécutifs est le temps d'exécution de l'application de la formule n*(n+1)/2, i.e. O(1). 🙂
    • Pas de. “la somme de la première n numéros consécutifs” est un description d'algorithme. Voilà qui contraste avec “la somme de la première n numéros consécutifs”. Celle-ci est concernée par le résultat. L'ex est intéressé à la méthode, c'est à dire la somme des nombres entiers, un par un. J'ai du fait que de plus en plus explicite que ...
    • Bien sûr, c'est une question de terminologie. Et puisqu'il n'est pas une description formelle, mais juste une conversation, il peut être adaptée au contexte dépendait. Mais dans la plupart des contextes au cours d'une conversation "en additionnant les n premiers nombres consécutifs" ou similaire n'est pas un algorithme - c'est un tâche (un problème à résoudre). Pas tout particulier de mise en œuvre (algorithme) pour résoudre cette tâche, mais la tâche elle-même. Et en parlant de temps de la complexité de la tâche est de parler du temps de la complexité du meilleur algorithme pour le résoudre (dans la conversation parce que, à strictement parler, seulement l'algorithme peut avoir des temps d'exécution).
    InformationsquelleAutor Konrad Rudolph
  3. 7

    n(n+1)/2 est le moyen rapide de calculer la somme d'un consécutives de la séquence de N entiers (à partir de 1). Je pense que vous êtes confus d'un algorithme avec le grand-oh notation!

    Si vous avez pensé à elle comme une fonction, puis de la grande-oh la complexité de cette fonction est en O(1):

    public int sum_of_first_n_integers(int n) { 
return (n * (n+1))/2; 
}

    De la naïveté de mise en œuvre aurait grand-oh complexité de O(n).

    public int sum_of_first_n_integers(int n) {
  int sum = 0;
  for (int i = 1; i <= n; i++) {
    sum += n;
  }
  return sum;
}

    Même simplement en regardant chaque cellule d'un unique n-par-n est la matrice O(n^2), puisque la matrice a n^2 cellules.

    • Je pense que ce n'est pas expliquer ce qui est réellement demandé: “Comment se fait la somme des n premiers nombres entiers est O(n^2)”?
    InformationsquelleAutor Julius Musseau
  4. 4

    Donc je suppose que c'est en fait une référence à Les fissures de Codage Interview, qui a du présent paragraphe sur un StringBuffer mise en œuvre:

    Sur chaque concaténation, une nouvelle copie de la chaîne est créé, et l'
    deux chaînes de caractères sont copiés sur, caractère par caractère. La première
    itération nous demande de copie x caractères. La deuxième itération
    nécessite copier 2x caractères. La troisième itération nécessite 3x, et
    ainsi de suite. Le temps total est donc O(x + 2x + ... + nx). Cela réduit
    pour O(xn²). (Pourquoi n'est-il pas O(xnⁿ)? Parce que 1 + 2 + ... n est égal à n(n+1)/2
    ou, O(n²).)

    Pour quelque raison que ce soit, j'ai trouvé cela un peu déroutant lors de ma première lecture, trop. L'important est que n multiplie les n, ou en d'autres termes que n² qui se passe, et qui domine. C'est pourquoi, en fin de compte O(xn²) est juste O(n²) -- le x est une sorte de red herring.

    • avec "n2 qui se passe, et que domine" tout fait "clic", merci!
    InformationsquelleAutor Alex Moore-Niemi
  5. 2

    Il n'est pas vraiment la complexité d'un problème, mais plutôt une complexité d'un algorithme.

    Dans votre cas, si vous choisissez de parcourir tous les nombres, la complexité est, en effet, O(n).

    Mais ce n'est pas le plus efficace algorithme. Plus efficace est d'appliquer la formule - n*(n+1)/2, qui est constante, et donc la complexité est O(1).

    InformationsquelleAutor Luchian Grigore
  6. 1

    Vous avez une formule qui ne dépend pas du nombre de nombres à ajouter, c'est donc un constante de temps algorithme, ou O(1).

    Si vous ajoutez chaque numéro un à la fois, alors il en est de O(n). La formule est un raccourci, c'est un autre algorithme plus efficace. Le raccourci fonctionne lorsque les numéros sont ajoutés tous les 1..n. Si vous avez un non-contigus de la séquence de nombres, puis le raccourci formule ne fonctionne pas et vous devrez revenir à l'un par un algorithme.

    Rien de tout cela s'applique à la matrice de nombres, si. L'addition de deux matrices, il est toujours en O(n^2) parce que vous êtes l'ajout de n^2 paires de nombres pour obtenir une matrice de n^2 résultats.

    InformationsquelleAutor Rob Kennedy
  7. 0

    Il y a une différence entre la sommation de N des entiers arbitraires et en additionnant N qui sont tous dans une rangée. Pour 1+2+3+4+...+N, vous pouvez profiter du fait qu'ils peuvent être divisés en paires avec une commune de la somme, par exemple, 1+N = 2+(N-1) = 3+(N-2) = ... = N + 1. Donc, c'est N+1, N/2 fois. (Si il y a un nombre impair, l'un d'eux sera dissociée, mais avec un peu d'effort, vous pouvez voir que la même formule tient dans ce cas.)

    Qui n'est pas O(N^2), si. C'est juste une formule qui utilise N^2, en fait O(1). O(N^2) signifie (en gros) que le nombre d'étapes pour calculer elle pousse comme N^2, pour les grandes N. Dans ce cas, le nombre d'étapes est la même quel que soit N.

    InformationsquelleAutor Tim Goodman
  8. 0

    réponse de la somme de la série de n naturel peut être trouvé à l'aide de deux façons. première méthode consiste à ajouter tous les nombres dans la boucle. dans ce cas, l'algorithme est linéaire et le code sera comme ceci

     int sum = 0;
     for (int i = 1; i <= n; i++) {
     sum += n;
   }
 return sum;

    elle est analogue à 1+2+3+4+......+n. dans ce cas, la complexité de l'algorithme est calculé comme le nombre de fois que plus l'opération est réalisée, qui est O(n).

    deuxième moyen de trouver une réponse de la somme de la série de n nombre naturel est direst la formule n*(n+1)/2. cette formule utilisent la multiplication au lieu d'une répétition de plus. opération de multiplication n'a pas le temps linéaire de la complexité. il existe différents algorithme disponible pour la multiplication, qui a le temps de la complexité allant de O(N^1.45) à O (N^2). par conséquent, en cas de multiplication du temps de la complexité dépend du processeur de l'architecture. mais pour l'analyse du temps de la complexité de la multiplication est considéré comme O(N^2). donc quand on utilise la deuxième méthode pour trouver la somme puis le temps de complexité O(N^2).

    ici opération de multiplication est pas le même que l'opération d'addition. si quelqu'un a connaissance de l'informatique de l'organisation objet, alors il peut facilement comprendre le fonctionnement interne de multiplication et d'addition de l'opération. la multiplication de circuit est plus complexe que le circuit additionneur et nécessitent beaucoup plus de temps que le circuit additionneur pour calculer le résultat. donc, le temps de la complexité de la somme de la série ne peut pas être constante.

    • Je pense que vous confondez le nombre d'opérations avec le nombre de chiffres dans un nombre. Si vous définissez n le nombre d'opérations, dans le premier cas, vous devez effectuer n sommes, therefire complexitiy est O(n). Dans le second cas, le coût serait en O(1) depuis que vous êtes en fait effectuer une fixe et connue certain nombre d'opérations (3 dans cette formule).
    InformationsquelleAutor Ashok