Что мы можем сделать лучше всего с кодированием длины пробега.
На этой странице показано, что сложность по времени составляет O (m * n), где m - количество повторений числа.
Является ли более эффективный алгоритм для выполнения RLE?
Я думаю, вы, возможно, неправильно поняли время выполнения. Алгоритм на странице википедии - O (n) (где n - длина ввода). Обратите внимание, что индекс одинаков для обоих циклов и увеличивается.
Как уже говорилось, временная сложность составляет O (n). Более эффективные алгоритмы используют SIMD или CUDA для обработки более одного элемента одновременно.
Вы можете взглянуть на эффективную и быструю реализацию: TurboRLE: кодирование длины выполнения , включая SIMD. Также предоставляется эталонная программа.