運行長度編碼

Question

運行長度編碼可以做的最好的事情是什麼。

This page表明的時間複雜度是O（m * n個），其中m是時間的重複數目的數目..

是對更有效的算法做RLE？

Answer 1

我想你可能誤解了運行時。維基百科頁面上的算法是O（n）（其中n是輸入的長度）。注意兩個循環的索引是相同的，並且增加。

Answer 2

如前所述，時間複雜度爲O（n）。更高效的算法使用SIMD或CUDA一次處理多個元素。

您可能會看到一個高效且快速的實現：TurboRLE:Run Length Encoding包括SIMD。還提供了基準程序。