Discussion :

[souviron34]

Bonjour

Petite question d'un non-théoricien :

quand on définit une complexité en O(N logN), le log est-il décimal ou népérien (par exemple dans un tri quicksort) ?

Je suis bien d'accord qu'en termes généraux on s'en fiche, c'est la forme qui compte.

Mais si l'on veut comparer la complexité de 2 implémentations d'un algorithme, où pour l'un le facteur est logN et pour l'autre c'est autre chose mais d'assez petit (par exemple en fonction d'une autre variable), il peut être intéressant de savoir si on compare avec log népérien ou log décimal : logn (10) = 2.3, log10(10) = 1

On a donc plus d'un facteur 2 entre les 2...

[deltree]

J'aime bien les questions stupides, parce qu'on peut donner des réponses stupides

Le facteur n'apparait pas dans une formule de complexité ainsi o(2n) est la même complexité que o(n).
et comme log (x) = ln(x)/ln(10) (j'avoue j'ai cherché pour retrouver le formule) O(n.Log(n) ) = O(n.ln(n) * (1/ln(10)) <=> O(n.ln(n) ) car (1/ln(10) est une constante

Les facteurs ne servent pas car la complexité sert à donner l'accroissement en fonction de la taille du problème qui dépend de l'algo uniquement, mais pas à donner une mesure de temps, qui dépend aussi de l'implem (j'ai un doute si je suis clair ...)

[Franck Dernoncourt]

Cela dépend de l'algorithme. Regarde http://en.wikipedia.org/wiki/Master_theorem, c'est une des méthodes les plus utilisés pour calculer la complexité d'un algorithme récursif : tu verras que selon les appels récursifs, la base du logarithme varie. Par exemple, merge sort et quicksort seront de base 2.

Néanmoins comme tu le soulignes, ainsi que deltree, O(kf(n)) = O(f(n)) (où k est une constante, n lié à la taille de l'input, f une fonction quelconque), donc en pratique la base du logarithme n'importe peu car il y aura probablement d'autres constantes cachées ailleurs, et en outre on sort du concept big O.

Le livre http://algo.developpez.com/livres/#L2100039229 chapitre 4 explique très bien l'apparition des log dans l'analyse de la complexité des algorithmes récursifs.

Voici en gros l'idée :

[souviron34]

je sais bien cela, mais ce qui me pose problème c'est quand par exemple on regarde des algos tels que :

Bentley & Ottmann algorithm

the Bentley–Ottmann algorithm takes time O((n + k) log n).

Si donc on compare 2 méthodes, on peut donc avoir à "estimer" un k par rapport à un log.. (dans ce cas-ci, initialement k est < N, mais cependant le k n'est pas vraiment connu ni à proprement parlé une "variable")

Et dans ce cas savoir qu'il y a un facteur 2 peut fortement influencer sur la conclusion...



C'est encore plus vrai quand on regarde les différentes optimisations dont cet algo a été l'objet :

O(n log n + k), and this problem of arrangement construction was solved deterministically in the same O(n log n + k) time bound by Chazelle & Edelsbrunner (1992). However, constructing this arrangement as a whole requires space O(n + k), greater than the O(n) space bound of the Bentley–Ottmann algorithm; Balaban (1995) described a different algorithm that lists all intersections in time O(n log n + k) and space O(n).

If the input line segments and their endpoints form the edges and vertices of a connected graph (possibly with crossings), the O(n log n) part of the time bound for the Bentley–Ottmann algorithm may also be reduced. As Clarkson, Cole & Tarjan (1992) show, in this case there is a randomized algorithm for solving the problem in expected time O(n log* n + k), where log* denotes the iterated logarithm, a function much more slowly growing than the logarithm. A closely related randomized algorithm of Eppstein, Goodrich & Strash (2009) solves the same problem in time O(n + k log(i)n) for any constant i, where log(i) denotes the function obtained by iterating the logarithm function i times. The first of these algorithms takes linear time whenever k is larger than n by a log(i)n factor, for any constant i, while the second algorithm takes linear time whenever k is smaller than n by a log(i)n factor. Both of these algorithms involve applying the Bentley–Ottmann algorithm to small random samples of the input.

On a donc bien que ce soit des "constantes" (k) ou des fonctions (log(i)n ou klog(i)n) dépendantes d'une "constante"... dont les différentes optimisations comparent la valeur...

[Franck Dernoncourt]

je sais bien cela, mais ce qui me pose problème c'est quand par exemple on regarde des algos tels que :

Bentley & Ottmann algorithm

Si donc on compare 2 méthodes, on peut donc avoir à "estimer" un k par rapport à un log.. (dans ce cas-ci, initialement k est < N, mais cependant le k n'est pas vraiment connu ni à proprement parlé une "variable")

N'a-t-on pas plutôt 0 ≤ k < n² au lieu de 0 ≤ k ≤ n ?
(où n est le nombre de lignes et k le nombre d'intersections)

[souviron34]

N'a-t-on pas plutôt 0 ≤ k < n² au lieu de 0 ≤ k ≤ n ?
(où n est le nombre de lignes et k le nombre d'intersections)

Peut-être...

Mais le fond du problème n'est pas vraiment là..

Que ce soit celui-là ou des équivalents, l'expression de la complexité (et de la comparaison entre diverses optimisations) peut visiblement s'exprimer en fonction d'une "contante" qui n'est pas vraiment une variable, et donc la "valeur" détermine la différence entre 2 solutions..

Admettons (ce n'est pas le cas, mais...) que je veuille proposer une optimisation à cet algo.

Il faudrait donc que je prouve que je puisse obtenir mieux que :

linear time whenever k is larger than n by a log(i)n factor, for any constant i, while the second algorithm takes linear time whenever k is smaller than n by a log(i)n factor

Si donc j'avais un moyen de dire que "k is larger than n by a log(n)/2" à la place de "k is larger than n by a log(n) factor" (ce qu'ils font en élevant le log à la puissance i) , j'aurais donc un meilleur algo..

Et encore, ici je compare les mêmes choses.

Mais si dans un cas c'est "log(n)", et dans l'autre c'est "k", il faudrait bien que je compare k et log(n) (si par exemple on comparait O(n log(n)) à O(n k), ou, mieux, à O(n + k))

D'où mon questionnement...

[pseudocode]

je sais bien cela, mais ce qui me pose problème c'est quand par exemple on regarde des algos tels que :

the Bentley–Ottmann algorithm takes time O((n + k) log n).

Si donc on compare 2 méthodes, on peut donc avoir à "estimer" un k par rapport à un log.. (dans ce cas-ci, initialement k est < N, mais cependant le k n'est pas vraiment connu ni à proprement parlé une "variable")

Et dans ce cas savoir qu'il y a un facteur 2 peut fortement influencer sur la conclusion...

?

Les paramètres (k,n,...) de la fonction O sont des paramètres liées aux données d'entrée. Ca n'a pas vraiment de sens de les comparer avec une constante liée a l'implémentation d'une technique du calcul.

La complexité d'un algo n'a de sens que si elle fait abstraction de l'implémentation, et qu'elle ne se préoccupe que des données d'entrées.

[souviron34]

La complexité d'un algo n'a de sens que si elle fait abstraction de l'implémentation, et qu'elle ne se préoccupe que des données d'entrées.

ben voui, mais là par exemple dans l'algo cité le nombre d'intersections n'est pas une "donnée" à proprement parlé puisque justement on va les trouver..

On ne connaît pas k quand on lance l'algo..

(c'est un peu comme les calculs de complexité en fonction de la taille de sortie http://en.wikipedia.org/wiki/Output-sensitive_algorithm)

[Franck Dernoncourt]

k est toutefois un paramètre propre à l'input (et non de l'algorithme), même si il n'est pas connu au départ.

Etant donné que k peut être Ω(n), alors l'écriture O((n + k) log n) est sensée (c'est la raison pour laquelle je soulignais que nous avions 0 ≤ k < n² au lieu de 0 ≤ k ≤ n, bien qu'ayant lu le tout rapidement je l'avais mis sous forme interrogative afin de vous inciter à vérifier).

Voici un exemple de complexité non sensée car faisant apparaître un paramètre propre à l'algorithme (et non à l'input), que j'avais relevé dans une présentation faite sur un article proposant une variante d'un algorithme de clustering classique : (slide 46)
[ame="http://www.scribd.com/doc/38388055/2010-Presentation-Automated-Variable-Weighting-in-K-Means-Type-Clustering"]2010 - Presentation - Automated Variable Weighting in K-Means Type Clustering[/ame]


PS : la prévisualisation des liens Scribd marche-t-elle chez quelqu'un ? Sinon si quelqu'un veut l'article original, me contacter à franck.dernoncourt@gmail.com, je ne peux malheureusement pas le mettre en ligne car copyrighté...
P²S : je suis conscient que "k peut être Ω(n)" est un abus de langage