java - 在算法的上下文中，什么构成 'array access'？

Question

下面是来自教科书的 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;
  }

Answer 1

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 ²c) 算法，它可能会增长 1,000,000 倍。 (严格来说，任何 O(nc) 算法也是 O(n²c)，因为它只是一个限制，但我们先不谈这个。)