Производительность анализа массивов с использованием Arrays.sort - PullRequest
Новая
       14

Производительность анализа массивов с использованием Arrays.sort

0 голосов
/ 01 февраля 2012

У меня есть код, который использует Arrays.sort(char[]) следующим образом: 

    void arrayAnalysis(String[] array){
      for(int a=0; a<array.length;a++){
        char[] letters = array[a].toCharArray();
        Arrays.sort(letters);
        ...
        for(int b=a+1; b<array.length;b++){
          char[] letters2 = array[b].toCharArray();
          Arrays.sort(letters2);

          if(Arrays.equals(letters, letters2)
            print("equal");
        }
      }
    }

В этом случае n равно размеру массива.Из-за вложенных циклов, производительность автоматически O (n ^ 2).Тем не менее, я думаю, что Arrays.sort (с O (nlog (n))) также влияет на производительность и делает ее хуже, чем O (n ^ 2).Правильно ли это мышление?

Будет ли окончательный результат O (n * nlog (n) * (n * nlog (n))? Или я ухожу?

Спасибо.

Редактировать: я должен добавить, что, хотя n относится к размеру массива, Arrays.sort работает с количеством букв в элементе массива, что является частью моей путаницы, если это следует добавить к анализу производительности.

Edit2: Было бы здорово, если бы голосующий оставил комментарий о том, почему это было сочтено плохим вопросом.

Ответы [ 2 ]

5 голосов
/ 01 февраля 2012

Если n - это длина массива, а m - это длина каждой array[i], то на каждой из n^2 итераций вы будете выполнять сортировку O(m log m), так что в целом это O(n^2 (m log m)) (или O(n^3 log n), если n == m. [ПРАВКА: теперь, когда я думаю об этом больше, ваше предположение верно, и это неправильная сложность. Но то, что я говорю ниже, все еще верно!]]

Хотя это и не обязательно. Вы могли бы просто сделать отсортированную копию массива и сделать свой вложенный цикл for, используя этот. Посмотрите, что происходит, когда a равно 0: сначала вы сортируете array[0], затем во внутреннем цикле for вы сортируете от array[1] до array[n].

Затем, когда a равен 1, вы сначала сортируете array[1], а затем во внутреннем цикле for с array[2] по array[n]. Но вы уже отсортировали все это , и это не так, как если бы оно изменилось за это время.

2 голосов
/ 01 февраля 2012

Вы запускаете n внешних циклов, каждый из которых запускает n внутренних циклов, каждый из которых вызывает O ( n log n ) алгоритм, поэтому конечный результат - при отсутствии какого-либо взаимодействия между уровнями - это O ( n 3 log n ).

...