Run length encoding - algorithme, indépendant de la langue, exécution

Quel est le meilleur que nous puissions faire avec le codage de longueur d’exécution.

Cette page suggère que la complexité temporelle est O (m * n) où m est le nombre de fois où le nombre se répète.

Est-ce que l'algorithme est plus efficace pour faire du RLE?

Réponses:

Je pense que vous avez peut-être mal compris le runtime. L'algorithme sur la page wikipedia est O (n) (où n est la longueur de l'entrée). Remarquez comment l'index est le même pour les deux boucles et augmente.

Comme déjà indiqué, la complexité temporelle est O (n). Des algorithmes plus efficaces utilisent SIMD ou CUDA pour traiter plusieurs éléments à la fois.

Vous pouvez jeter un coup d'œil à une implémentation efficace et rapide: TurboRLE: Encodage de longueur d'exécution y compris SIMD. Un programme de référence est également fourni.