это мой первый вопрос, поэтому я надеюсь, что не нарушил никаких правил. Мне, наконец, удалось написать код для алгоритма сортировки Radix, но мне интересно, сделал ли я это неправильно. Что заставляет меня думать, что мой алгоритм выглядит сложнее O (n^3), но Radix Sort - это, как правило, O (k.n) алгоритм. Я вычисляю сложность моего алгоритма неправильно или просто написал действительно плохой код?radix sort (java implementation) сложность
private static void radixSort(int[] A){
ArrayList<Integer>[] bucket = new ArrayList[10];
int maxNumberOfDigits = 0;
for(int number : A){
if(numberOfDigitsIn(number) > maxNumberOfDigits) maxNumberOfDigits = numberOfDigitsIn(number);
}
for(int c=0; c<bucket.length; c++){
bucket[c] = new ArrayList<Integer>();
}
int i = 0;
int digit;
int j;
while(i < maxNumberOfDigits){
for(j = 0; j<A.length; j++){
digit = getDigit(A[j], i);
bucket[digit].add(A[j]);
}
int index = 0;
for(int z = 0; z<bucket.length; z++){
for (int k=0; k<bucket[z].size(); k++){
A[index] = bucket[z].get(k);
index += 1;
}
bucket[z].clear();
}
i += 1;
}
}
Методы getDigit() и numberOfDigitsIn() имеют постоянное время.
Я думаю, вам стоит попробовать [Обзор Core] (http://codereview.stackexchange.com/) –
@ ɐuıɥɔɐɯ Этот вопрос не выглядит так, как если бы он был очень хорош для [codereview.se ]. Этот вопрос, похоже, требует объяснения или проверки временной сложности кода. Кажется, что искатель ищет обзор кода. – nhgrif
http://pastie.org/8674341#11 вот решение O (k.n), которое у меня было для него. однако он использует рекурсию. –