Plus précisément, l'ascension en côte Steepest-Ascent, l'escalade stochastique et le recuit simulé. La complexité du temps généralisé serait bien aussi. Merci.Quelle est la complexité temporelle de l'algorithme d'escalade en côte?
Les méthodes que vous répertoriez peuvent être interrompues à tout moment et renvoyer "le meilleur résultat jusqu'à présent". Par conséquent, il est logique de parler du temps qu'ils prennent pour retourner le meilleur résultat absolu (le maximum global).
Toutes les méthodes listées peuvent ne pas atteindre le maximum global. Par conséquent, leur complexité est O (∞).
Les notions de complexité temporelle traditionnelle n'ont pas de sens pour les heuristiques, seulement pour les algorithmes appropriés. Voici a writeup about the difference between the two.
merci beaucoup! –
Cela dépend du nombre de collines, comme le souligne Pascal. Cependant, comme il ne l'a pas mentionné, il sera au pire linéaire avec 'O (n)' et au mieux peut être 'O (log n)' en utilisant une réinitialisation aléatoire. – yekta
Cette question semble être hors-sujet parce qu'elle concerne la théorie plutôt que la programmation. –
@jim Si vous allez le fermer parce que c'est hors sujet, il serait utile de laisser une référence pour savoir où il est approprié de poster une telle question. Essayez http://cs.stackexchange.com/ pour des questions théoriques la prochaine fois. – yekta