analyse temporelle de l'algorithme «taille d'entrée» vs «éléments d'entrée»

Je suis toujours un peu confus avec les termes "longueur d'entrée" et "taille d'entrée" lorsqu'ils sont utilisés pour analyser et décrire la limite supérieure asymptomatique d'un algorithme

Il semble que la longueur d'entrée de l'algorithme dépende en grande partie du type de données et de l'algorithme dont vous parlez.

Certains auteurs se réfèrent à la longueur d'entrée à la taille des caractères qui sont requis pour représenter l'entrée, donc "abcde" si utilisé comme jeu d'entrée dans un algorithme aura une "longueur d'entrée" de 6 caractères.

Si au lieu des caractères, nous avons un nombre (des entiers par exemple), alors parfois la représentation binaire est utilisée à la place des caractères, de sorte que la "longueur d'entrée" est calculée comme $N*log(L)$ (étant L le nombre Max dans l'ensemble d'entrée) .

Il y a d'autres problèmes qui, même si l'ensemble d'entrée sont des nombres, décrivent la "longueur d'entrée" comme des "variables de décision", donc pour un ensemble d'entrée de longueur N avec des nombres compris entre $0-2^{32}$ la longueur d'entrée est juste N ( sous-ensemble par exemple), ou encore compliquer le nombre de valeurs de place binaires qu'il faut pour énoncer le problème (ce que je crois est exactement la même chose que $N*log(L)$ )

Donc:

• cela dépend de l'algorithme?
• Que signifie et quand utiliser chaque longueur d'entrée "version"
• Y a-t-il une règle que je peux utiliser pour décider laquelle utiliser?

Dans le sens le plus formel, la taille de l'entrée est mesurée en référence à une implémentation Turing Machine de l'algorithme, et c'est le nombre de symboles alphabétiques nécessaires pour coder l'entrée.

C'est bien sûr plutôt abstrait, et il est très difficile de travailler avec dans la pratique, ou du moins très ennuyeux - nous aurions besoin de réfléchir à la façon dont nous allons spécifier les délimètres, etc. etc. une mesure indirecte de la taille de l'entrée - quelque chose de plus pratique et accessible, mais cela ne pose aucun problème mathématique dans notre analyse.

En utilisant votre exemple "abcde", il serait normalement le cas que l'alphabet que nous utilisons pour l'entrée soit petit, donc même en utilisant la mesure proxy de caractères, nous savions que même sur une machine de Turing, nous pouvons, si cela nous dérangeait, spécifiez un codage d'entrée qui convertirait "abcde" en une forme codée dont la longueur ne dépasse pas 5 × c pour une constante c . Cette expansion d'une constante ne ferait généralement aucune différence dans notre analyse asymptotique, car nous rejetons régulièrement les facteurs constants.$5$$5\times c$ $c$

Dans un autre cas, nous mesurons souvent la taille d'un graphe d'entrée par le nombre de sommets . Clairement, si nous voulons spécifier des graphes arbitrairement grands, la taille de l'entrée codée n'est pas simplement n - qu'est-il arrivé aux bords, par exemple? Ce que nous savons, c'est que nous pouvons utiliser un schéma de codage raisonnable qui représente le graphe en N = c ⋅ n 2 log n bits. C'est un peu plus une expansion que constante, mais dans de nombreux cas intéressants, nous ne traitons que des choses à une granularité de polynômes, et les polynômes se composent bien de nombreuses façons - en particulier, par exemple, si nous déterminons que notre temps de course est O ( p $n$$n$$N = c\cdot n^{2}\log n$ où p est un polynôme, alors nous savons qu'il existe un polynôme p ′ tel que O ( p ( n ) ) = O ( p ′ ( N ) ) , donc quand nous revenons à la mesure formelle de l'entrée , nous sommes toujours en temps polynomial.$O(p(n))$$p$$p'$$O(p(n)) = O(p'(N))$

Un endroit où cela pourrait tomber est lorsque vous travaillez avec des nombres. Comme un nombre de magnitude peut être codé en n = O ( log m ) bits, si notre temps de fonctionnement était O ( m ) , ce serait O ( 2 n ) - exponentiel dans la taille d'entrée réelle - ce qui rendrait la magnitude m un mauvais choix pour un proxy pour la taille d'entrée si nous voulions parler d'appartenance à P par exemple (quand vous arrivez à Fortement- N P -complet et Faiblement- N $m$$n = O(\log m)$$O(m)$$O(2^{n})$$m$$\mathcal{P}$$\mathcal{NP}$$\mathcal{NP}$-complet, rappelez-vous cela). D'un autre côté, si tout ce qui nous intéressait était la décidabilité, ce serait une mesure de substitution assez bonne.

Ainsi, bien qu'il n'y ait pas de règle déclarée pour choisir une mesure proxy pour la taille d'entrée, l'exigence est que l'expansion ou la contraction de la taille proxy par rapport à la taille d'entrée soit compatible avec ce que vous essayez de prouver. En règle générale, les changements de facteurs constants n'ont presque jamais d'importance, les petits facteurs polynomiaux sont normalement bien et fonctionnent pour la plupart de la théorie de base que vous voyez, les grands facteurs polynomiaux peuvent toujours fonctionner pour la théorie, mais peuvent être une mauvaise surprise dans la pratique, et les quantités exponentielles de changement sont normalement beaucoup trop extrêmes.

Cela dépend de votre modèle de calcul et aussi du malheureusement parfois de l'algorithme lui-même.

• Si votre modèle de calcul est une machine de Turing , la taille de l'entrée est le nombre de cellules occupées par l'entrée. Donc, si votre entrée est alors l'entrée a une longueur de 6.$ababcd$
• Si votre modèle est la RAM, la taille de l'entrée est le nombre de registres / cellules de mémoire où l'entrée reste initialement. Cela pourrait être utilisé à mauvais escient car vous pourriez techniquement écrire la totalité de l'entrée dans un registre. Cependant, les calculs sont plus coûteux si vous utilisez le modèle des coûts logarithmiques.
• Si votre modèle de calcul est un mot-RAM , vous comptez également les cellules de mémoire, mais elles ne peuvent stocker que des entiers bits, w étant un paramètre de votre modèle.$w$$w$

Cependant, de nombreux algorithmes ne sont pas mesurés par rapport à la taille d'entrée "réelle". Ensuite, vous devez regarder attentivement à quoi fait référence l'énoncé de l'analyse.

• $O(n\log n)$$n$$O(1)$$n$
• $n\times n$

$n$