"Le coût de l'algorithme X est linéaire dans la zone de la plus grande ellipse utilisée?" Cela signifie-t-il que le coût des algorithmes X augmente linéairement à mesure que la surface de l'ellipse augmente?Que signifie cette déclaration sur les algorithmes?
Notez, que la zone de l'ellipse est augmentée en doublant, ce qui signifie exponentielle, non?
Si A est la zone, l'algorithme sera O (A).
Si vous considérez (x/a)^2 + (y/b)^2 = 1 alors votre algo sera O (a * b)
Si vous doublez la zone d'ellipse à chaque itération de votre algorithme, vous aurez une croissance quadratique de la surface, mais la complexité totale O (An) où An est la région au cours de la dernière itération
EDIT
Je vais un peu en profondeur:
Votre algo fera f = A0 + A1 + ... + Une opération s où Ai est la zone au i-ième itération on peut réécrire la formulation en tant que f = A0 + 2 * A0 + 4 * A0 + ... + 2^n * A0
O (f) = O (2^n * A0) où 2^n * A0 = un
Jetez aussi un coup à https://en.wikipedia.org/wiki/Big_O_notation
Ne serait-ce pas 'O (a^2 + b^2)', pas 'O (a * b)'? –
La zone ellipse pourrait être écrite comme A = PI * a * b –
@NicolaPezzotti pouvez-vous élaborer un peu plus sur cette partie de votre réponse "mais la complexité totale sera O (An) où An est la zone au cours de la dernière itération ". pourquoi la complexité totale dépend de la zone lors de la dernière itération? Une explication simplifiée serait plus facile à comprendre pour moi. Pardonnez mon ignorance et mon manque de connaissances dans ce domaine.: '( –
La zone d'une ellipse est quadratique (N^2), non exponentielle (2^N). L'instruction signifie que le coût est une fonction linéaire de N où la zone est une fonction N^2.
Un nitpick: O (N^2), quand N et M sont dans le même ordre. –
Je ne suis pas d'accord. Le coût est une fonction linéaire de _N_, où la zone est également une fonction linéaire de _N_. –
dans chaque itération de l'algorithme, la zone de l'ellipse est augmentée en le doublant, c'est pourquoi j'ai dit qu'il est augmenté exponentiellement @ zim-zamo'pootertoot –
Pour les deux premiers paragraphes, elle doit être juste - mais qu'est-ce que vous entendez par la dernière phrase? –
@ZiyaoWei dans chaque itération de l'algorithme, la zone de l'ellipse est augmentée en le doublant, c'est pourquoi je l'ai dit est augmenté exponentiellement –
@WolfgangKuehne Lorsque nous parlons du coût de la complexité des algorithmes, il est toujours supposé que le coût de l'algorithme peut être représenté comme une fonction avec un certain nombre d'entrées. Ainsi, par exemple, si nous avons un algorithme 'f (n)', nous pourrions dire 'f croît linéairement', ce qui signifie que si' n' double, alors 'f' double et ainsi de suite. Dans ce cas, vous parlez de la zone de l'ellipse ... dont la valeur change _during_ l'algorithme. Cela n'a pas vraiment de sens dans la définition canonique du «coût» d'un algorithme. Si vous pouvez calculer le coût par rapport à la zone initiale, alors cela aurait du sens. – rliu