Bonjour, je suis en train d'étudier l'algorithmique, et je dois trouver le temps d’exécution de certains algorithmes (pour être plus précis, le "tight upper bound", donc - il me semble - O(n) qui éaglise tetra(n)).

Voici les algos :
http://pastebin.com/wt9mVc2d

Pour le moment, j'ai trouvé ça :
1.
for loop : O(n)
multiplication : O(log(n))
addition : O(1)
Fonction : O(nlog(n))

2. Q Array :
for loop : O(n)
insert in array : O(1)
extract min : O(n)
Fonction : O(n^2)

2. Q Heap :
for loop : O(n)
insert in heap : O(log(n))
extract min : O(log(n))
Fonction : O(n*log^2(n)) = O(n*log(n))

3.
fonction 1 : O(nlog(n))
fonction 2:
for loop : O(m)
Insert in array : O(1)
fonction 1 : O(nlog(n))
fonction : O(mnlog(n))

Je ne suis pas vraiment sûr de moi cependant, est-ce juste ?
Je voudrais juste savoir si je m'y prends de la bonne manière, cela n'étant pas non plus expliqué de manière explicites dans mes cours

Bonjour,

« il me semble - O(n) qui éaglise tetra(n)). » ceci n'a absolument aucun sens. Donc je vais la refaire. Quant tu veux connaître le coût d'un algorithme, tu peux vouloir calculer plusieurs choses :
le nombre exact d'opération (mais c'est long et fastidieux)
une borne supérieure sur le nombre d'opérations
un ordre de grandeur pour cette borne supérieure : on dit alors que « l'algo est en O(f(n)) », ce qui signifie que le coût sera « au pire quelques f(n) »
une borne inférieure sur le nombre d'opérations
un ordre de grandeur pour cette borne inférieure : on dit alors que « l'algo est en Ω(g(n)) », ce qui signifie que le coût sera « au mieux quelques g(n) »
et enfin un ordre de grandeur du nombre d'opérations en général quand c'est possible (si f(n) = g(n) en gros) : on dit alors que l'algo est en Θ(f(n)), ce qui signifie que le coût sera « toujours quelques f(n) ».

Souvent, on se contente du O(...) parce que le Ω(...) (et donc le Θ(...)) sont très difficile à déterminer. Cela dit, en l'absence d'appel de fonction dans une seule branche d'un if et en l'absence de break/continue dans les boucles, on peut normalement déterminer le Θ(...), ce qui est mieux.

Dans ton cas, je trouve :

1. Θ(n²) tel que c'est écrit (et Θ(n) en Haskell car il va faire optimiser le calcul de la ligne 5 automatiquement).

2. O(n²) avec un tableau, O(n.log(n)) avec un tas.

3a. Θ(n.log(n)) ... ce qui est naze parce que je sais faire en ≃ 3n/2. (il faudrait que je regarde si Haskell arrive à optimiser ce code là tient )

3b. Θ(m.n.log(n)).

Bonjour,

tout d'abord merci pour l'aide !

Après quelques recherche, j'ai trouvé ceci : Definition (Tightness) Consider a function f(n)=O(g(n)). If for every function h(n) such that f(n)=O(h(n)) it is also true that g(n)=O(h(n)), then we say that g(n) is a tight asymptotic bound on f(n).
Mais je vais prendre dans la meme idée que les solutions que tu as demandé.

J'aimerai savoir comment as-tu trouvé Θ(n²) pour le premier ? La boucle for fait O(n), mais d'où vient le second ?

Merci encore pour l'aide

« d'où vient le second ? » de la ligne 5. Moi je ne sais pas faire un produit de i entiers quelconques en moins de i-1 opérations. Ça donne un Θ(i) (et non un Θ(1) ou un O(log(n)) ).

Ok je comprends, merci

Putain moi je pige que dalle