Позволяет разбить ваш код на разделы:
List<BigInteger> newValues = new ArrayList<BigInteger>();
String[] newValuesArray = new String[unsorted.length];
for (int i = 0; i < unsorted.length; i++) {
newValues.add(new BigInteger((unsorted[i])));
}
Производительность этого раздела зависит от двух вещей:
- Размер
unsorted
. - Длина строк в
sorted
.
Причина, по которой длины строк имеют значение, заключается в том, что преобразование десятичной строки во внутреннее представление, используемое BigInteger
, является дорогостоящим.Для одной строки с D цифрами сложность времени равна O (D 2 ).Таким образом, общая сложность составляет O (ND 2 ).
Collections.sort(newValues);
Этот шаг сортировки обычно O (NlogN) или O (NlogND) в худшем случае 1 .
for (int i = 0; i < newValues.size(); i++) {
newValuesArray[i] = newValues.get(i).toString();
}
Это O (ND 2 ) из-за вызова toString()
.
Итак, в целом мы имеем типичную сложность:O (ND 2 + NlogN).
( Анализ сложности довольно груб и готов. Если я допустил какие-либо серьезные ошибки, пожалуйста, прокомментируйте ... )
Из вышеприведенного анализа видно, что стоимость преобразований из строк в BigInteger
и обратно может доминировать в стоимости сортировки.Особенно, если большинство чисел имеет много цифр.
Можем ли мы избежать этого?Да!Можно написать Comparator<String>
, который может сравнивать десятичные числа без преобразования их в двоичные.
Второе, что мы могли бы оптимизировать, - это сортировка.
В некоторыхВ некоторых случаях метод Collections::sort
фактически копирует коллекцию в массив, сортирует массив, а затем копирует отсортированный массив обратно в список.
Существует еще один метод с именем Arrays::sort
.Если вы воспользуетесь этим, вы сможете избежать одного или нескольких шагов копирования списка <-> массива.
Существует еще один метод с именем Arrays::parallelSort
.Если есть доступные ядра C, использование этого метода может привести к (до) ускорению C-кратного.
1 - Типичный случай возникает, когда числа всписок значительно отличается, и вы можете сравнить их пару в O (1).Наихудший случай - когда все числа одинаковы (или близки), и для сравнения обычно используется O (D).