2015-04-26 18 views
1

это мой первый вопрос, поэтому я надеюсь, что не нарушил никаких правил. Мне, наконец, удалось написать код для алгоритма сортировки 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() имеют постоянное время.

+0

Я думаю, вам стоит попробовать [Обзор Core] (http://codereview.stackexchange.com/) –

+0

@ ɐuıɥɔɐɯ Этот вопрос не выглядит так, как если бы он был очень хорош для [codereview.se ]. Этот вопрос, похоже, требует объяснения или проверки временной сложности кода. Кажется, что искатель ищет обзор кода. – nhgrif

+0

http://pastie.org/8674341#11 вот решение O (k.n), которое у меня было для него. однако он использует рекурсию. –

ответ

0
for(int z = 0; z<bucket.length; z++){ 
     for (int k=0; k<bucket[z].size(); k++){ 

Решающим моментом здесь является то, что сумма всех размеров ковша будет равна п, так что эти петли комбинироваться только принимать O (п). Цикл над j принимает O (n), а цикл while на i будет выполняться для итераций maxNumberOfDigits, и это число представляет k в описанной вами O (kn) времени исполнения. Таким образом, общее число, фактически, O (kn).