どのようなアルゴリズムのコンテキストで 'アレイアクセス'を構成する？
以下は、JavaのLSD基数ソートの実装で、各文字列に正確に W 文字が含まれる文字列の配列をソートするためのテキストブックです。
実行時に配列アクセスの数を数えたいと思います。私はLSDソートが n * c 配列へのアクセスを必要としていると読んでいる。 n は文字列の数であり、 c 各文字列にしかし、以下のアルゴリズムは、複数の配列に複数回アクセスします。これらのそれぞれでカウンタを増やすと、重要な要素 nc になります。
では、アルゴリズムのコンテキストでは、正確には「配列アクセス」を構成するものは何ですか？ここで数える必要があると考えられる配列アクセスのインスタンスは1つだけですか、実際はこの例は、必要以上に多くの配列アクセスを使用する非効率的な実装ですか？
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;
}
LSDソートは、n回の文字列の数と各文字列の文字数のn回のc回の配列アクセスを必要とすると読みました。
あなたはそれが O（nc）であると読んでいないでしょうか？それはまったく同じことではありません。 big-O表記です。重要な点は、配列アクセスの正確な数を判断することではなく、 n としてどのように成長するか（あるいは、成長する方法の制限） c が増加します。この場合、それは線形に増加します - もしあなたが n を1000倍に増やすと、合計コストは1000倍も増加すると予想します。 2 ）アルゴリズムではなく、1,000,000倍になる可能性があります。 （厳密に言えば、O（nc）アルゴリズムもそれが限界であるために O（n 2 ）です。
最初のforループ内のすべての配列アクセスは、基本的に配列アクセスの合計数としてカウントされます。 nは、これらの組み合わせられた配列アクセスを何回行うのかです。これは、アクセスの実際の数ではなく、関数の成長のおおよその考え方を示します。
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;
}
配列 'アクセス'は、読み取りまたは書き込みのいずれかです...
