行程编码
What is the best we can do with run length encoding.
This page suggests the time complexity is O(m*n) where m is the number of time the number repeats..
Is the a more efficient algorithm to do RLE?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我认为您可能误解了运行时。维基百科页面上的算法是 O(n)（其中 n 是输入的长度）。请注意两个循环的索引是如何相同的，并且不断增加。
I think you maybe mis-understood the runtime. The algorithm on the wikipedia page is O(n) (where n is the length of the input). Notice how the index is the same for both loops, and increasing.
正如已经说过的，时间复杂度是 O(n)。更高效的算法使用 SIMD 或 CUDA 一次处理多个元素。
您可能会看一下高效快速的实现：TurboRLE:Run Length Encoding 包括SIMD。还提供了基准程序。
As already stated the time complexity is O(n). More efficient algorithms use SIMD or CUDA to process more than one element at a time.
You might have a look at an efficient and fast implementation: TurboRLE:Run Length Encoding including SIMD. A benchmark program is also provided.