Что представляет собой «доступ к массиву» в контексте алгоритмов?

Question

Ниже приведена реализация сортировки LSD Radix в Java из учебника для сортировки массива строк, где каждая строка содержит ровно 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)? Это совсем не одно и то же. Это обозначение big-O . Суть не в том, чтобы определить точное количество обращений к массиву, а в том, чтобы говорить о том, как он растет (точнее, предел того, как он может расти) при увеличении n или c. В этом случае оно увеличивается линейно - если вы увеличите n в 1000 раз, вы ожидаете, что общая стоимость тоже вырастет в 1000 раз ... тогда как если бы это было O (n ^{2 *) 1014 * в) алгоритм вместо этого может возрасти в 1 000 000 раз. (Строго говоря, любой алгоритм O (nc) также O (n 2 c), потому что он только предел, но давайте не будем вдаваться в это.)}

Answer 2

В Big-O в асимптотической записи число обращений пропорционально константе. Когда вы анализируете код, все константы отбрасываются.

В случае Radix Sort Большой O равен O(cn). Но если вы хотите фактически посчитать, сколько раз был получен доступ к массиву, вам нужно умножить это число на некоторую константу k, где это k является специфическим для конкретной кодированной реализации.

Например, эта функция O(n), но число обращений к массиву равно 2n: один для чтения значения и один для его обновления. Число 2 отбрасывается.

for (i=0; i<N; i++)
   A[i] = A[i] + 1;

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

Все обращения к массиву внутри первого цикла for по существу считаются как общее число обращений к массиву, так что это ваш c.N - сколько раз вы выполняете эти обращения к комбинированным массивам.Это дает вам приблизительное представление о росте функции, а не фактическое количество обращений.