comment S'affecter la complexité?

Disons que nous avons un tableau de 1.000.000 d'éléments et de nous les passer tous en revue pour vérifier quelque chose de simple, par exemple si le premier caractère est "Une". De mon (très peu), de la compréhension, de la complexité sera O(n) et il faudra un certain montant de X temps. Si j'ajoute un autre SI (pas d'autre si) pour vérifier, disons que, si le dernier caractère est "G", comment peut-elle changer la complexité? Il double la complexité et le temps? Comme O(2n) et 2X?

Je voudrais éviter de prendre en considération le nombre de calculs différentes commandes ont à faire. Par exemple, je comprends que Len() nécessite plus de calculs pour nous donner le résultat que d'un simple char comparaison n', mais disons que les commandes utilisées dans l'IFs aura (presque) la même quantité de complexité.

OriginalL'auteur Evripidis Bourlas | 2013-06-04

  1. 12

    O(2n) = O(n). La généralisation, O(kn) = O(n), avec k étant une constante. Bien sûr, avec deux Fi, il peut prendre deux fois plus de temps, mais le temps d'exécution sera toujours une fonction linéaire de la taille de l'image.

    Modifier: Ici est une explication, avec des exemples, de la grande-O notation qui n'est pas trop mathématique orientée

    je vous remercie beaucoup. J'étais à défaut de comprendre la relation entre la complexité et le temps.
    Excellent lien, je pensais que je savais Big O avant, maintenant je le sais!

    OriginalL'auteur dario_ramos

  2. 4

    Complexité asymptotique (qui est ce que big-O utilise) ne dépend pas de facteurs constants, plus précisément, vous pouvez ajouter /supprimer des tout facteur constant vers /à partir de la fonction, et il restera équivalent (i.e. O(2n) = O(n)).

    Dans l'hypothèse d'un si-déclaration prend un temps constant, il ne fera qu'ajouter un facteur constant de la complexité.

    Une "constante de temps" signifie:

    • Le temps pris pour que, si l'instruction pour un élément donné ne dépend pas de combien d'autres il y a d'éléments dans le tableau
    • Donc en gros si il n'a pas d'appeler une fonction qui regarde à travers les autres éléments dans le tableau, d'une certaine façon ou quelque chose de semblable à ce
    • Non-appel de fonction si l'instruction est probablement pas un problème (sauf s'il contient une déclaration qui passe par le tableau, dont certains de la langue le permet)

    Donc 2 (constante de temps) si les relevés appelée pour chaque élément de O(2n), mais c'est égal à O(n) (eh bien, il pourrait ne pas être vraiment 2n, plus que dans la note complémentaire).

    Voir Wikipédia pour plus de détails et une définition plus formelle.

    Remarque: Outre de ne pas être tributaire de facteurs constants, c'est aussi ne dépend pas asymptotiquement plus petits termes (termes qui restent plus petites indépendamment de la façon dont big n obtient), par exemple, O(n) = O(n + sqrt(n)). Et big-O est juste une limite supérieure, donc dire que c'est O(n9999) serait également correct (bien que se disant que, dans un test ou de l'examen sera probablement que vous obtenez 0 marques).

    Remarque supplémentaire: Le problème quand pas en ignorant les facteurs constants est - ce qui le classe comme une unité de travail? Il n'y a pas de définition standard ici. Une façon est d'utiliser l'opération la plus longue, mais la détermination de ce qui peut ne pas être toujours simple, ni ne serait-il toujours être particulièrement précis, ni seriez-vous en mesure générique comparer les complexités des algorithmes différents.

    OriginalL'auteur Dukeling

  3. -2

    C'est lié à une question que j'ai posté moi-même aujourd'hui.

    Dans votre exemple, il dépend de si vous pouvez passer de la première à la dernière élément et si vous ne pouvez pas puis ça dépend aussi de la durée moyenne de chaque entrée.

    Si vous êtes allé vers le bas à travers la matrice que vous avez eu à lire chaque entrée, afin d'évaluer vos deux si les déclarations alors que votre commande soit O(1 000 000 de xN) où N est la longueur moyenne de chaque entrée. SI N est variable, alors il aura une incidence sur la commande. Un exemple serait la multiplication où nous effectuons des Log(N) ajouts d'une entrée qui est Log(N) de longueur et ainsi de l'ordre de O(Log^2(N)) ou si vous préférez O((Log(N))^2).

    D'autre part, si vous pouvez il suffit de cocher le premier et le dernier caractère, alors N = 2 et est constante, alors il peut être ignoré.

    C'est un point IMPORTANT que vous devez être prudent, car comment pouvez-vous déterminer si votre multiplicateur peut être ignoré. Par exemple, disons que nous faisions Log(N) ajouts de Log(N/100). Maintenant, juste parce qu'Log(N/100) est le plus petit terme ne signifie pas que nous ne pouvons l'ignorer. Le facteur multiplicateur ne peut être ignorée si elle est variable.

    -1 Constante facteurs n'ont aucun effet sur la complexité. Ils peuvent influer sur le réel observé les performances d'exécution (et sérieusement), mais qui est une chose différente.
    Comme j'ai essayé de faire clair, cela dépend de ce que votre lecture est un facteur constant. Par exemple si vous faites N itérations et votre "constante" facteur est N, alors vous NE peut tout simplement pas ignorer que la N comme une constante. Si c'était le cas de la multiplication serait un Log(N) cette opération n'est pas un Log(N^2). La constante de ce que je dis doit être petite par rapport à votre nombre d'itérations. Je dois ajouter que, dans ce cas N n'est pas une constante, car il dépend, comme je l'ai dit sur la taille moyenne des éléments du tableau qui est une autre variable. Vous pouvez définir un fixe une limite supérieure de ce qui est de ce que vous faites avec le pire des cas de toute façon
    Je pense que nous sommes la croix-affichage. Vous avez manqué mon edit? N est une autre variable, il n'est pas une constante et je n'ai pas l'appeler un dans mon premier post, j'ai seulement fait ici parce que vous avez mentionné. Appelons ça le multiplicateur. Le point est que le multiplicateur ne peut être ignoré si petit par rapport à ce qu'elle se multiplie. Oups ferraille que je vois je n'ai appeler une constante à la fin. N'était pas ce que je voulais dire. Je veux dire multiplicateur mais quand j'ai édité et ajouté que la note finale j'ai fait une erreur.
    Je crois que je vois ce que tu veux dire maintenant, mais votre formulation est toujours incorrecte. Si N est une constante, il peut être ignoré pour la complexité, peu importe comment elle est grande. Si N n'est pas une constante mais dépend de la taille de l'entrée, il ne peut pas être ignoré. Cela est vrai même si le terme est faible par rapport au terme principal de la complexité. Même un log(N) croît vers l'infini pour N grand, alors vous ne devez pas l'ignorer! Petits et grands sont les mauvais catégories ici. C'est à peu près constant ou non constants.
    Oui je vois ce que tu veux dire au sujet de mauvais texte, on devrait dire aussi longtemps que le facteur de multiplication est variable, il ne peut pas être ignoré, bien que j'ai des soucis qui confond les gens trop parce que nous ne pouvons ignorer une petite variables quand ils ne touchent pas à la grande complexité comme si nous nous ajouter une autre variable qui, nous le savons, seront relativement faibles. Par Exemple O(Log(N^2) + Log(N)) = O(Log(N^2)).

    OriginalL'auteur Rhuaidhri Tynan