问题描述
下面是Java中的LSD基数排序实现从教科书到字符串数组排序，每个字符串恰好包含是W 字符。
我要算阵列的数量在运行时访问。我读过LSD排序是应该要求 N *ç数组访问其中 N 是一个字符串的数量， C 每个字符串中的字符数量。然而，该算法如下访问多个阵列数次。如果我递增计数器的每一项我会拥有一个显著系数 NC 。
那么究竟是什么构成了算法的情况下'数组访问'？是否有只有一个被认为是更显著，我应该在这里算，还是这个例子，其实是使用更多的数组访问超过必要的低效执行数组访问实例？
公众诠释lsdSort（String []数组，INT W）{
INT访问= 0;
//排序[]领先W¯¯字符。
INT N = array.length;
的String [] AUX =新的String [N];
为（中间体D = W-1 d取代; = 0; D--）
{//排序方式对DTH字符键索引计数。
INT []数=新INT [R + 1]; //计算频率计数。
的for（int i = 0; I＆n种;我++）{
算上[数组[我] .charAt（D）+ 1] ++;
}
对于（INT R = 0; R＆LT; R，R ++）{
//变换计数指标。
算上[R + 1] + =计数[R]。
}
的for（int i = 0; I＆n种;我++）{
// 分发。
AUX [计[数组[我] .charAt（D）] +] =阵列[I]
}
的for（int i = 0; I＆n种;我++）//复制回。
数组[我] = AUX [I]
}
返回访问;
}
你确定你没有看过，它的 O（NC）？这是不一样的东西都没有。这是大O记法。关键不是确定确切的数字的数组访问 - 这是谈论如何成长（或者说，限制的它是如何成长）为 N 或 C 增加。在这种情况下，线性增加 - 如果增加 N 通过的1000倍，你只会想到总成本的1000倍增长过...而如果它是一个为O（n C）算法相反，它可能是由1,000,000倍增长。 （严格来说任何O（NC）算法的也是的为O（n C），由于它仅是一个极限，但我们不要进入这一点。）
Below is an LSD Radix sort implementation in Java from a textbook to sort an array of strings where each string contains exactly W characters.
I want to count the number of array accesses during runtime. I've read that LSD sort is supposed to require n * c array accesses where n is the number of strings and c the amount of characters in each string. However, the algorithm below accesses more than one array several times. If I increment a counter at each of these I'll end up with a significant factor of nc.
So what exactly constitutes 'array access' in the context of algorithms? Is there only one instance of array access that is considered more significant that I should count here, or is this example in fact an inefficient implementation that uses more array access than necessary?
public int lsdSort(String[] array, int W) {
int access = 0;
// Sort a[] on leading W characters.
int N = array.length;
String[] aux = new String[N];
for (int d = W-1; d >= 0; d--)
{ // Sort by key-indexed counting on dth char.
int[] count = new int[R+1]; // Compute frequency counts.
for (int i = 0; i < N; i++) {
count[array[i].charAt(d) + 1]++;
}
for (int r = 0; r < R; r++) {
// Transform counts to indices.
count[r+1] += count[r];
}
for (int i = 0; i < N; i++) {
// Distribute.
aux[count[array[i].charAt(d)]++] = array[i];
}
for (int i = 0; i < N; i++) // Copy back.
array[i] = aux[i];
}
return access;
}
Are you sure you haven't read that it's O(nc)? That's not the same thing at all. It's big-O notation. The point isn't to determine the exact number of array accesses - it's to talk about how it grows (or rather, the limit of how it can grow) as n or c increase. In this case it increases linearly - if you increase n by a factor of 1000, you would only expect the total cost to grow by a factor of 1000 too... whereas if it were an O(nc) algorithm instead, it might grow by a factor of 1,000,000. (Strictly speaking any O(nc) algorithm is also O(nc) due to it only being a limit, but let's not get into that.)
这篇关于是什么构成了算法的情况下'数组访问'？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！