Exécution de tri basée sur la comparaison par rapport au nombre total de bits d'entrée

Question

Les algorithmes de tri basés sur la comparaison sont baissés par $ Omega (nlogn) $, où $ n $ est le nombre d'éléments dans la liste des entrées.

Cependant, lorsqu'il s'agit de différents modèles de calcul, tels que des algorithmes qui traitent des opérations arithmétiques (euclid-gcd) ou, $ n $, la taille de l'entrée, n'est plus le nombre d'éléments mais le nombre total de bits requis pour représentent l'entrée. Dans ces cas, la complexité du temps est mesurée comme le nombre d'opérations de bits nécessaires en ce qui concerne le nombre total de bits dans l'entrée.

Regarder le poste Qu'est-ce que le temps pseudo-polynomial en quoi diffère-t-il du temps polynomial?

Le temps polynomial est défini comme:

Un algorithme fonctionne en temps polynomial si son temps d'exécution est O (xk) pour une certaine constante K, où X désigne le nombre de bits d'entrée donnés à l'algorithme.

Le temps pseudo-polynomail est défini comme:

Un algorithme s'exécute en temps pseudo-polynomial si l'exécution est un polynôme dans la valeur numérique de l'entrée, plutôt que dans le nombre de bits requis pour le représenter.

Regarder Comment pouvons-nous supposer que les opérations de base sur les nombres prennent constamment du temps?

Pour la taille des mots $ w = theta (logn) $, les opérations arithmétiques standard sur ces mots prennent $ o (1) $ de temps, par définition.

Avec ces définitions à l'esprit, j'ai du mal à voir comment certains algorithmes de tri basés sur la comparaison sont du temps polynomial en ce qui concerne les deux $ N $, le nombre d'éléments dans l'entrée et $ x $, le nombre total de bits dans l'entrée; Le premier post que j'ai référencé fait cette affirmation.

Pourquoi ils sont polynomiaux par rapport à $ n $ est assez évident, donc je ne examinerai que la représentation bit de l'entrée $ x $ pour les algorithmes de tri basés sur une comparaison avec 2 complexités de temps différentes.

Fusionner ou tri rapide sur une liste de $ n $ éléments

Nous avons besoin de $ w = theta (logn) $, tel que défini dans CLR, puisque nous devons au moins être en mesure d'indexer dans un tableau de taille $ n $. En supposant que tous les éléments correspondent à un mot, ce qui, je pense, est une hypothèse raisonnable ici, $ x = wn = theta (nlogn) $. S'il vous plaît laissez-moi savoir si mon $ x $ est faux !!!

Étant donné que le temps d'exécution était $ o (nlogn) $, la complexité du temps par rapport à $ x $ est $ o (x) $. Je vais interpréter cela comme un sens que nous avons besoin d'un nombre linéaire d'opérations sur le nombre total de bits nécessaires pour représenter cette liste d'entrée.

Sélection sur une liste d'éléments $ n $:

Je supposerai le même $ x = wn = theta (nlonn) $ pour la taille d'entrée. Le temps d'exécution est $ o (n ^ 2) $. Ici, j'ai besoin d'aide: comment écrire la durée de fonctionnement proprement en termes de $ x $, comme je l'ai fait pour fusion / tri rapide ci-dessus? Le premier post que j'ai référencé vient d'utiliser $ w = 32 $ bits et j'ai facilement obtenu $ o (x ^ 2)Comment pouvons-nous supposer que les opérations de base sur les nombres prennent constamment du temps?) et les CLR ont souligné que $ W $ n'est pas une constante mais $ theta (logn) $.

J'ai une question similaire pour Tri de comptage, qui n'a pas encore été répondu. premier poste J'ai fait référence aux réclamations qu'il est exponentiel en ce qui concerne $ x $ sans la condition $ k = theta (n) $ lorsque $ x = theta (nlogk) $ bits, mais j'ai du mal à changer de $ o (n + k) $ en termes de $ x $. S'il vous plaît aider !!