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

Question

下面是一个用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增加.在这种情况下,它会线性增加 - 如果你增加n1000倍,你只能期望总成本增长1000倍...而如果它是一个O(n ² c)算法,它可能会增长1,000,000倍.(严格地说,任何O(nc)算法也是 O(n ² c),因为它只是一个限制,但是我们不能进入.)