下面是来自教科书的 Java 中的 LSD 基数排序实现，用于对字符串数组进行排序，其中每个字符串恰好包含 W 个字符。
我想统计运行时访问数组的次数。我读过 LSD 排序应该需要 n * c 数组访问，其中 n 是字符串的数量，c 是字符的数量在每个字符串中。然而，下面的算法多次访问多个数组。如果我在每个计数器上增加一个计数器，我最终会得到一个重要的 nc 因子。
那么在算法的上下文中究竟是什么构成了“数组访问”？是否只有一个数组访问实例被认为更重要，我应该在这里计算，或者这个例子实际上是一个低效的实现，使用了比必要更多的数组访问？
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;
}
最佳答案
I've read that LSD sort is supposed to require n times c array accesses where n is the number of strings and c the amount of characters in each string.
你确定你没有读到它是 O(nc) 吗？那根本不是一回事。这是big-O notation .重点不是确定数组访问的确切次数 - 而是讨论它如何增长(或者更确切地说，它如何增长的限制)作为 n 或c 增加。在这种情况下，它线性增加——如果你将 n 增加 1000 倍，你只会期望总成本也增长 1000 倍......而如果它是 O(n 2c) 算法，它可能会增长 1,000,000 倍。 (严格来说，任何 O(nc) 算法也是 O(n2c)，因为它只是一个限制，但我们先不谈这个。)
关于java - 在算法的上下文中，什么构成 'array access'？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/7923230/