什么构成算法上下文中的“数组访问”？

下面是一个用Java编写的LSD Radix排序实现，用于对一个字符串数组进行排序，其中每个字符串都包含正好的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; } 

Answer 1

我已经读过LSD排序应该需要n次c数组访问，其中n是字符串数，c是每个字符串中的字符数。

你确定你没有读过它是O(nc)吗？ 这根本不是一回事。 这是一个很大的符号 。 关键不在于确定数组访问的确切数量 – 当n或c增加时，它要谈论它如何增长（或者更确切地说，它的增长方式）。 在这种情况下，它会线性增加 – 如果你将n增加1000倍，你只能期望总成本增长1000倍…而如果它是一个O（n ² c）算法，那么它可能会增长1,000,000倍。 （严格地说，任何O（nc）算法也是 O（n ² c），因为它只是一个限制，但我们不能进入。）

Answer 2

第一个for循环内的所有数组访问基本上都算作数组访问的组合数，所以这就是你的c。 n是您执行这些组合数组访问的次数。 这使您可以大致了解函数的增长，而不是实际的访问计数。

Answer 3

 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]++; access++; access++; } for (int r = 0; r < R; r++) { // Transform counts to indices. count[r+1] += count[r]; access++; } for (int i = 0; i < N; i++) { // Distribute. aux[count[array[i].charAt(d)]++] = array[i]; access++; access++; access++; } for (int i = 0; i < N; i++) // Copy back. array[i] = aux[i]; access++; access++; } return access; } 

数组'access'是读取或写入...

Answer 4

在Big-O渐近符号中，访问次数与常数成比例。 分析代码时，将丢弃所有常量。

在Radix Sort的情况下，Big O是O(cn) 。 但是如果你想实际计算访问数组的次数，你需要将该数乘以某个常数k ，其中k特定于具体的编码实现。

例如，此函数为O(n)但访问数组的次数为2n ：一个用于读取值，另一个用于更新它。 数字2被丢弃。

 for (i=0; i