Existe-t-il des problèmes dont l'algorithme le plus connu a exécuté le temps

Je n'ai jamais vu d'algorithme avec un journal dans le dénominateur auparavant, et je me demande s'il existe des algorithmes réellement utiles avec ce formulaire?

Je comprends beaucoup de choses qui pourraient entraîner la multiplication d'un facteur de journalisation pendant l'exécution, par exemple des algorithmes de tri ou d'arborescence, mais qu'est-ce qui pourrait vous amener à diviser par un facteur de journalisation?

La réponse habituelle à "qu'est-ce qui pourrait vous amener à diviser par un journal?" est une combinaison de deux choses:

1. un modèle de calcul dans lequel les opérations arithmétiques à temps constant sur les entiers de taille de mot sont autorisées, mais dans laquelle vous voulez être prudent sur la longueur des mots, vous supposez donc bits par mot (car moins que cela et vous ne pouviez même pas traiter toute la mémoire, et aussi parce que les algorithmes qui utilisent les recherches de table prendraient trop de temps pour configurer les tables si les mots étaient plus longs), et$O(\log n)$
2. un algorithme qui comprime les données en compressant les bits en mots, puis opère sur les mots.

Je pense qu'il existe de nombreux exemples, mais l'exemple classique est l' algorithme des quatre Russes pour les sous-séquences communes les plus longues, etc. Il finit par être , car il utilise l'idée de compression de bits mais enregistre ensuite une seconde facteur de log en utilisant une autre idée: remplacer les blocs d'opérations O ( log 2 n ) bits par une seule recherche de table.$O(n^2/\log^2 n)$$O(\log^2 n)$

Le Rubik's Cube est un exemple très naturel (et pour moi, inattendu). Un cube $n\times n\times n$ nécessite $\Theta(n^2/\log n)$ étapes à résoudre. (Notez qu'il s'agit d'une notation thêta, c'est donc une limite supérieure et inférieure stricte).

Ceci est illustré dans cet article [1].

Il peut être utile de mentionner que la complexité de la résolution d'instances spécifiques du cube de Rubik est ouverte, mais conjecturée pour être NP-dure (discutée ici par exemple) NP hard [2]. Le $\Theta(n^2/\log n)$ algorithme garantit une solution, et il garantit que toutes les solutions sont asymptotiquement optimales, mais il peut ne pas résoudre de manière optimale des instances spécifiques. Votre définition d'utile peut s'appliquer ou non ici, car les cubes de Rubik ne sont généralement pas résolus avec cet algorithme ( l'algorithme de Kociemba est généralement utilisé pour les petits cubes car il donne des solutions rapides et optimales dans la pratique).

[1] Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Anna Lubiw et Andrew Winslow. Algorithmes de résolution des cubes de Rubik. Actes du 19e Symposium européen annuel sur les algorithmes (ESA 2011), 5–9 septembre 2011, pages 689–700

[2] Erik D. Demaine, Sarah Eisenstat et Mikhail Rudoy. Résoudre le Rubik's Cube de manière optimale est NP-complet. Actes du 35e Symposium international sur les aspects théoriques de l'informatique (STACS 2018), 28 février-3 mars 2018, pages 24: 1-24: 13.

Un exemple de apparaissant dans le dénominateur sans astuces d'emballage de bits est un article récent d' Agarwal, Ben Avraham, Kaplan et Sharir sur le calcul de la distance discrète de Fréchet entre deux chaînes polygonales dans le temps O ( n 2 log log n / log n ) . Bien que je ne sois pas familier avec les détails de l'algorithme, une astuce générale consiste à partitionner l'entrée en morceaux relativement petits, puis à combiner intelligemment les réponses (bien sûr, cela ressemble à diviser pour mieux régner, mais vous n'obtenez pas le journal n au dénominateur avec quelques astuces astucieuses)$\log n$$O(n^2\log\log n/\log n)$

Pas exactement ce que vous avez demandé, mais une situation "à l'état sauvage" dans laquelle un facteur logarithmique apparaît dans le dénominateur est le document " Pebbles and Branching Programs for Tree Evaluation " de Stephen Cook, Pierre McKenzie, Dustin Wehr, Mark Braverman et Rahul Santhanam.

Le problème d'évaluation d'arbre (TEP) est: étant donné un arbre -ary annoté avec des valeurs en { 1 , … , k } sur les feuilles et les fonctions { 1 , … , k } d → { 1 , … , k } sur les nœuds internes , évaluez l'arbre. Ici, chaque nœud interne obtient la valeur de sa fonction annotée sur les valeurs de ses enfants. C'est un problème facile, et le but est de montrer qu'il ne peut pas être résolu dans l'espace logarithmique (lorsque la hauteur de l'arbre fait partie de l'entrée). À cet effet, nous nous intéressons à la taille des programmes de branchement résolvant TEP.$d$$\{1,\ldots,k\}$$\{1,\ldots,k\}^d \to \{1,\ldots,k\}$

Dans la section 5, des limites strictes sont présentées pour les arbres de hauteur 3, à la fois pour TEP et pour le problème connexe BEP, dans lequel la sortie est réduite à de manière arbitraire. Pour TEP, la borne est Θ ( k 2 d - 1 ) , tandis que pour BEP, la borne est Θ ( k 2 d - 1 / log k ) , c'est-à-dire que vous obtenez une sauvegarde de log k .$\{0,1\}$$\Theta(k^{2d-1})$$\Theta(k^{2d-1}/\log k)$$\log k$

Même s'il ne s'agit pas d'exécution, j'ai pensé qu'il valait la peine de mentionner le résultat classique de Hopcroft, Paul et Valiant: [1], car il est toujours en l'esprit de "ce qui pourrait vous faire économiser un facteur de journal."$\mathsf{TIME[t]} \subseteq \mathsf{SPACE}[t/\log t]$

Cela donne de nombreux exemples de problèmes dont la borne supérieure la plus connue de la complexité de l'espace a un journal dans le dénominateur. (Selon votre point de vue, je pense que cela rend cet exemple très intéressant - quel théorème étonnant! - ou très inintéressant - il n'est probablement pas "réellement utile".)

[1] Hopcroft, Paul et Valiant. Le temps contre l'espace . J. ACM 24 (2): 332-337, 1977.

Il existe deux problèmes avec une complexité de requête étroite :$\Theta(n/\log n)$

• Problème de pesage des pièces avec balance à ressort.
• Mastermind avec position n et 2 couleurs.

$n$$O((n/\log n)^2)$

William J. Masek, Mike Paterson: A Faster Algorithm Computing String Edit Distances. J. Comput. Syst. Sci. 20 (1): 18-31 (1980).

$\Theta(n/\log n)$ apparaît comme la limite correcte pour un problème considéré par Greg et Paul Valiant (pas de connexion aux trucs de bits):

Gregory Valiant et Paul Valiant, The power of linear estimators, 2011. In the 52nd Annual IEEE Symposium on the Foundations of Computer Science, FOCS 2011.

Voici un autre exemple d'une limite stricte ayant un facteur logarithmique. (Il s'agit du théorème 6.17 de Boolean Function Complexity: Advances and Frontiers de Stasys Jukna.)

La taille de la formule (sur la base binaire complète ou la base De Morgan) du problème de distinction des éléments est $\Theta(n^2/\log n)$, où $n$ est le nombre de bits dans l'entrée.

La raison pour laquelle le facteur logarithmique apparaît dans le dénominateur est $m$ entiers compris entre 1 et $\text{poly}(m)$ requires $n := O(m \log m)$ bits in total, since each integer requires $O(\log m)$ bits. So an upper bound that looks natural in terms of $m$, like $\Theta(m^2 \log m)$, becomes $\Theta(n^2/\log n)$ when expressed in terms of $n$, where $n$ is the number of bits in the input.

Finding the prime factors of n by trial division when the list of primes is already given. There are $\theta(\frac{n}{\log(n)})$ primes less than n so if these primes are given to you, then trial division of n by each of them takes $\theta(\frac{n}{\log(n)})$ time (assuming division is a constant-time operation)

somewhat similar to JG's answer & "thinking outside the box", this seems like a related/relevant/apropos/fundamental negative result. based on diagonalization with a universal TM, there exists a $O(f(n))$ DTIME language that cannot run in $O\left({f(n)\over{\log f(n)}}\right)$ DTIME, due to the time hierarchy theorem. so this applies to a linear DTIME algorithm that exists, $f(n)=n$, that runs impossibly in $O\left(n \over {\log n} \right)$ DTIME.