Calculer le temps d'exécution d'un algorithme

Bonjours, j'ai été sélectionné aux demi-finales et voulant m'entrainer pendant les 10 derniers jours avant l'épreuve, j'ai commencé à regarder les sujets des écrits. Mais je bloque sur une des questions:
Quel est le temps d’exécution de votre algorithme pour N = 4 et M = 6 sur votre iPhone 3GS, équipé
d’un processeur ARM à 600 MHz ?
(Question 9b, 2010 sujet mastermind)
Malgré des recherches sur internet, je n'est pas trouver comment calculer le temps d'exécution en fonction de la fréquence du processeur. Etant en première je n'est que très brièvement entendu parler de fréquence lors d'un cours sur l'étude des signaux électriques. Je sait aussi évaluer la complexité d'un algorithme mais sa à l'air un peu plus complexe.
Si vous avez un lien qui explique sa ou si quelqu'un se sent de me l'expliquer se serai sympa.

Merci d'avance

Alors, en gros :
1) Tu calcules la complexité de ton algo, par exemple : O((N\^2)*ln(N)) (où lg désigne le logarithme en base 2).
2) Tu remplaces N (et éventuellement les autres variables) de la formule dans ton O() par leurs valeurs (dans un sujet machine, tu as des contraintes maximales, du genre 1 tu remplaces N par 1000), ça te donne un nombre qui est l'ordre de grandeur des opérations "élémentaires" faites
3) Tu considères qu'un processeur à 1GHz peut faire environ 10 à 20 millions de ces opérations "élémentaires" par seconde.

Et voilà ! Après si tu obtiens un O(N) parce que tu parcours simplement un tableau, ou que tu as un O(N) parce que tu parcours un tableau 10 fois en faisant des comparaisons des comparaisons à chaque fois (pour avoir le maximum par exemple), évidemment les deux algorithmes ne mettront pas exactement le même temps. Mais cette méthode donne une très bon ordre de grandeur.

Merci beaucoup de ta réponse très rapide et assez claire.
J'ai juste une question concernant ton troisième point, pourquoi considérer qu'un processeur à 1 GHz peut faire 10 à 20 millions d'instructions par seconde? N'y a t-il pas un moyens d'avoir un nombre plus spécifique à partir de la fréquence?

Je pense que la question sert surtout à voir si t'as compris que ton algo tournera en 10 ms, 10 minutes ou 10 jours la méthode Artifère suffit pour ça.
Mais tu peux aussi coder en assembleur ARM lors de la demi et apprendre par cœur les specs de l'iPhone3GS. :|
D'ailleurs, je suis sur que les orgas, soucieux de la validité des réponses, recopient ton code et le font tourner sur un iPhone3GS. :p

Bon d'accord ;)
Merci de vos réponses en tout cas.
Pour l'iPhone j'y avait penser mais j'ai que le 3G pas le 3GS, les résultats auraient étés faussés \^\^

Processeur à 1GHz, ma foi, on m'a appris ça... Parce que sur france-ioi, il me semble que le serveur qui exécute le programme est à 1GHz. Bref, si t'as un processeur à 3 GHz par exemple, tu considères qu'il fait environ 30 à 60 millions d'opérations "élémentaires" par seconde. Si t'as un processeur à 600MHz, bah tu multiplies ce que je t'ai indiqué par 0.6.

Hum, j'viens de voir que j'ai mal lu ta question. En fait, j'appelle "opération élémentaire" (dans ce contexte), tout ce qui est du genre test (if), addition, multiplication, assignation d'une valeur à une variable, etc. Et bah apparemment, un processeur à 1GHz en fait environ 20 millions par seconde. Modulo le reste de l'infrastructure, et surtout le langage. Ce que j'ai donné, j'ai oublié de le préciser, est valable pour du C/C++. Le reste, je ne sais pas. Un langage interprété sera bien plus lent, par exemple.

1GHz, techniquement parlant, c'est un milliard de cycles d'horloge par seconde.
Après une instruction nécessite plus ou moins de cycles. Par exemple une addition dans un registre (donc si la variable est disponible en "cache" et pas dans la RAM) ne nécessite que très peu de cycles, mais certaines opérations peuvent en nécessiter des centaines.

Maintenant, il faut aussi considérer qu'une ligne dans ton code correspond en général à plus d'une instruction (exemple je récupère telle donnée à telle adresse dans la RAM pour la placer dans un registre, je lui additionne un nombre, je remet cette donnée dans la RAM...).

Calculer le nombre d'instructions et donc de cycles de manière exacte est impossible. On fait donc des moyennes pour simplifier. Celle d'Artifère, c'est de 50 à 100 cycles par instruction.
Tu donnes donc en gros (pas besoin de compter toutes les lignes) un nombre de cycles qu'utilise ton algo, et tu l'utilises avec ta complexité pour avoir un temps rapproché.

Tu trouveras un bon exemple de ce type de calcul dans cette correction de demi-finale : http://rakka.prologin.org/archives/2004/demi-finales/paris-lille/cor_etoile.pdf
Voilà le sujet initial correspondant : http://rakka.prologin.org/archives/2004/demi-finales/paris-lille/paris-lille.pdf

Merci beaucoup pour l'explication et les exemples,
je savais bien que la formule f = 1/T serai utile quelque part (mais pas où \^\^).
Je vais donc continuer à m'exercer.

A bientôt.