LSD字符串排序的复杂性(由Sedgewick& Wayne撰写的cfr。算法)

LSD字符串排序的复杂性(由Sedgewick& Wayne撰写的cfr。算法),第1张

在Sedgewick&amp ;;的算法中Wayne(第4版),他们声明LSD字符串排序使用7WN 3R数组访问和与N R成比例的额外空间来排序N个项目,其键是从R字符字母表中取出的W字符串。

他们通过这样说来证明这一点:“该方法是密钥索引计数的W次通过,除了aux []数组只被初始化一次。总数是从代码和提议A中立即进行的。”

然而,返回2页后,他们声明密钥索引计数使用11N 4R 1数组访问来稳定地对0和R-1之间的N项进行排序。

这怎么可能? LSD不应该是N W(4R 10N)吗?

为了清楚起见,我不是在寻找大O符号。

提前致谢!

密钥索引计数排序代码(根据算法):

int N = a.length;
int[] count = new int[R 1];
for (int i = 0; i < N; i  )
   count[a[i] 1]  ;
for (int r = 0; r < R; r  )
   count[r 1]  = count[r];
for (int i = 0; i < N; i  )
   aux[count[a[i]]  ] = a[i];
for (int i = 0; i < N; i  )
   a[i] = aux[i];

LSD字符串排序代码

int N = a.length;
int R = 256;
String[] aux = new String[N];
    for (int d = W-1; d >= 0; d--) 
    {

        int[] count = new int[R 1];
        for (int i = 0; i < N; i  )
            count[a[i].charAt(d)   1]  ;

        for (int r = 0; r < R; r  )
            count[r 1]  = count[r];

        for (int i = 0; i < N; i  )
            aux[count[a[i].charAt(d)]  ] = a[i];

        for (int i = 0; i < N; i  )
            a[i] = aux[i];
        }
    }
}

最佳答案:

0 个答案:

没有答案
本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复