Будет ли Arrays.sort() увеличивать временную и пространственно-временную сложность?

Существует проблема, связанная с массивом, требование состоит в том, чтобы временная сложность была O (n), а пространственная сложность - O (1).

Если я использую Arrays.sort(arr) и использую цикл for для одного цикла прохода, например:

public static int hello(int[]A){
  Arrays.sort(A);
  for(int i=0;i<A.length;i++){
     ....................
  }
  return ....;

}

Таким образом, цикл будет стоить O (n) времени. Мой вопрос: будет ли Arrays.sort() стоить больше времени? Если я использую Arrays.sort(), будет ли на этот раз сложность по-прежнему O(n)? И будет ли Arrays.sort() занимать больше места?


java arrays sorting time-complexity space-complexity
person aminy    schedule 21.03.2014    source источник
comment
Это не указывает используемый алгоритм сортировки, поэтому я не понимаю, как на него можно ответить.   -  person Robert Harvey    schedule 22.03.2014
comment
@RobertHarvey: Если только кто-то не предполагает, что Arrays.sort() использует некоторую магию, я думаю, что вопрос о том, какая минимальная временная сложность у него есть, вполне отвечает, не так ли?   -  person O. R. Mapper    schedule 22.03.2014
comment
Он указывает Arrays.sort, поэтому какой бы алгоритм он ни использовал. Трудно сказать, что это за язык (предположительно, Java), но стандартные библиотечные сортировки почти всегда являются сортировками сравнения.   -  person user2357112 supports Monica    schedule 22.03.2014
comment
@aminy: Что это за язык программирования?   -  person Robert Harvey    schedule 22.03.2014
comment
Это точно джава.   -  person Reuben Tanner    schedule 22.03.2014
comment
Просто немного головы. Если вам нужно время O(n) и пространство O(1), не используйте сортировку. Ни одна из реализаций сортировки в мире сейчас не работает за время O(n) и пространство O(1).   -  person Mohan    schedule 22.03.2014
comment
Несмотря на всю болтовню в разделе ответов ниже, ответ на ваш фактический вопрос - да: сортировка в среднем займет больше времени, чем O (n).   -  person Ernest Friedman-Hill    schedule 22.03.2014
comment
Предполагая, что вы достаточно знаете о сложности большого O, вам действительно следует спросить, что такое Arrays.sort временная и пространственная сложность?, что на самом деле является вопросом, который не требует никаких исследований, поскольку он довольно хорошо задокументирован.   -  person Bernhard Barker    schedule 22.03.2014
comment
Java Dual-Pivot Quicksort Time Complexity -> Лучшее — Ω(n), Среднее — θ(n logn), Худшее — O(n^2). Где худший случай встречается редко.   -  person Sathvik    schedule 12.10.2020

Ответы (5)


arrow_upward
34
arrow_downward

Я предполагаю, что вы говорите о Java здесь.

Таким образом, цикл будет стоить O (n) времени, мой вопрос в том, что Arrays.sort () будет стоить больше времени?

Да, Arrays.sort(int[]) во всех известных мне реализациях стандартной библиотеки Java является примером сортировки на основе сравнения и, следовательно, должен иметь сложность в наихудшем случае Ω(n log n). В частности, Oracle Java 7 использует вариант быстрой сортировки с двумя опорными точками для целочисленных перегрузок, который на самом деле имеет наихудший случай Ω(n2).

и будет ли Arrays.sort() занимать больше места?

По всей вероятности, он будет использовать пространство ω(1) (что означает еще одно да, использование пространства не равно O(1)). Хотя реализовать сортировку на основе сравнения только с постоянным дополнительным пространством можно, это крайне непрактично.

Тем не менее, при определенных условиях можно сортировать определенные типы данных за линейное время, см., например:

При постоянном диапазоне входных целых чисел (например, если abs(A[i]) <= C для некоторой константы C), то сортировка подсчетом и сортировка по основанию действительно используют только время O (n) и пространство O (1), так что это может быть полезно.

person Niklas B.    schedule 21.03.2014
comment
Согласно документам, тета (n log n) неверна для времени, а тета (1) неверна для пространства. мой пост содержит информацию из документов. - person Reuben Tanner; 22.03.2014
comment
@theSilentOne Я понятия не имею, о чем вы говорите, но я не думаю, что вы знаете, что означает Ω - person Niklas B.; 22.03.2014
comment
Имеется в виду нижняя граница. n log n не является нижней границей, согласно документам. - person Reuben Tanner; 22.03.2014
comment
@theSilentOne Да, это так. Извините, вы просто неправы в этом отношении. Вы правы, что он работает за O (n) для определенного класса входных данных, но в худшем случае это Ω (n log n) - person Niklas B.; 22.03.2014
comment
Эта реализация представляет собой стабильную, адаптивную, итеративную сортировку слиянием, которая требует гораздо меньшего количества сравнений, чем n lg(n), когда входной массив частично отсортирован, и в то же время обеспечивает производительность традиционной сортировки слиянием, когда входной массив упорядочен случайным образом. Если входной массив почти отсортирован, реализация требует примерно n сравнений, делая n нижней границей. - person Reuben Tanner; 22.03.2014
comment
@theSilentOne Вы, очевидно, не понимаете асимптотических сложностей. Я не собираюсь обсуждать это с вами дальше. - person Niklas B.; 22.03.2014
comment
Даже в первом предложении нижняя граница n lg(n) неверна. - person Reuben Tanner; 22.03.2014
comment
Поправьте меня, если я ошибаюсь, но говорить, что сортировка имеет нижнюю границу константного пространства, не имеет особого смысла - это относится к каждому отдельному алгоритму. - person Bernhard Barker; 22.03.2014
comment
@Dukeling извините, я имел в виду маленькую омегу. Фиксированный - person Niklas B.; 22.03.2014
comment
Никлас, предоставив вам возможность сомневаться в том, что я был неправ, я снова просмотрел нотацию Омеги и хотел бы поделиться тем, что я нашел. Если мы говорим, что f(n)=Ω(g(n)) u, мы имеем в виду, что для некоторой константы c›0 и всех достаточно больших n f(n)≥c g(n). В нашем обсуждении f(n) — это сложность timsort, а g(n) — это nlgn. Ваше утверждение Ω(n log n) будет означать, что timsort всегда занимает больше, чем nlogn, что явно неверно из документации. - person Reuben Tanner; 22.03.2014
comment
@theSilentOne Неверно, что асимптотическая сложность Ω (n log n) подразумевает отсутствие семейства входных данных, на которых алгоритм работает за O (n). Это означает, что существует константа c такая, что для всех n0 существует экземпляр I размера n ›= n0, для которого f(I) ›= cn * log н. Кстати, Timsort не используется даже для массивов int[] - person Niklas B.; 22.03.2014
comment
Вы не должны использовать фразу в худшем случае с омегой. А также с большим-о. Следует сказать, что сложность этой функции составляет O (n), а не сложность этой функции в худшем случае составляет O (n). Big-O уже рассчитан для наихудшего случая. Вы не можете определить омегу или тета относительно наихудшего случая. - person Onur Demir; 07.06.2020
comment
Мы обычно говорим о наихудшем случае в теоретическом CS, об этом не может быть и речи. Big-O полезен для определения верхних границ, а Omega полезен для определения нижних границ, что я и хотел здесь сделать. - person Niklas B.; 13.06.2020
comment
@Onur Я мог бы сказать, что эта функция имеет время выполнения O (2 ^ n), и это было бы правильно, но не очень полезно. - person Niklas B.; 13.06.2020

arrow_upward
7
arrow_downward

В соответствии с методом java jvm 8 javadocs метода Arrays.sort():

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

Таким образом, это увеличит вашу временную сложность с O (n) до O (n log (n))

person pedrogonzalezj    schedule 19.03.2018

arrow_upward
2
arrow_downward

Arrays.sort(int[] a) в последнем JDK реализован с помощью алгоритма быстрой сортировки Dual-Pivot, который имеет среднюю сложность O(n log n) и выполняется на месте (например, не требует дополнительного места).

person apangin    schedule 22.03.2014
comment
На самом деле это требует как минимум Ω(log n) дополнительного пространства. - person Niklas B.; 22.03.2014
comment
О, вы, вероятно, имеете в виду пространство стека выполнения. Тогда вы правы, но я думаю, что вопрос был о пространстве кучи. - person apangin; 22.03.2014

arrow_upward
2
arrow_downward

Это больше, чем O (n) времени и требует больше, чем O (1) места.

Arrays.sort() использует модифицированный < href="http://svn.python.org/projects/python/trunk/Objects/listsort.txt" rel="nofollow">Timsort в 1.7, который является относительно недавно разработанным алгоритмом сортировки и предлагает сортировка со сложностью x, где O (n) ‹ x ‹ O (nlgn) и пространство O (n/2)

person Reuben Tanner    schedule 22.03.2014
comment
Вы не совсем убедили меня в том, что мои утверждения вообще не имеют смысла, потому что я почти уверен, что они имеют смысл, но ваши комментарии побудили меня снова пересмотреть свои асимптотические сложности. - person Reuben Tanner; 22.03.2014
comment
@NiklasB., я обязательно скажу вам, что утверждение о том, что это была самая быстрая сортировка, было неверным. Недавно я прочитал статью об этом, и во многих случаях она работала лучше, чем быстрая сортировка или сортировка слиянием, поэтому самая быстрая казалась неуместной. Я полагаю, что вы, вероятно, лучше меня разбираетесь в теме асимптотических сложностей, но я знаю, что мои комментарии будут понятны любому инженеру-программисту, не имеющему докторской степени, и верны в соответствии с тем, что говорится в документации по Java. - person Reuben Tanner; 22.03.2014
comment
@theSilentOne Давай оставим это приятелю, без обид - person Niklas B.; 22.03.2014
comment
@НикласБ. Спасибо, сэр. Я также удалил свой детский голос против застенчивая ухмылка - person Reuben Tanner; 22.03.2014
comment
В Java стандартная реализация Arrays.sort(int[] a) использует быструю сортировку, а не Timsort. Поиск на основе объектов, поскольку он стабилен. Ссылки: docs.oracle .com/javase/7/docs/api/java/util/ и docs.oracle.com/javase/7/docs/api/java/util/. Стабильная реализация сортировки массивов объектов является обязательной в Java. - person Cahit Gungor; 09.01.2017
comment
@CahitGungor, только перегрузки Arrays.sort, которые работают с примитивами, используют QuickSort. Перегрузки, которые работают с объектами, используют адаптацию сортировки списка Тима Питерса для Python (TimSort). - person Reuben Tanner; 10.01.2017

arrow_upward
0
arrow_downward

Поскольку вы говорите об этом на языке Java, временная сложность наверняка увеличится с O (n) до O (nlogn). Это связано с тем, что в Java 8 Arrays.sort() реализован в алгоритме быстрой сортировки Dual-Pivot, а не в Single Pivot. Так что это требует дополнительного времени. И пространственная сложность O (1) невозможна, так как для этого требуется больше места, я думаю, O (n/2).

person Tek Raj Awasthi    schedule 01.06.2021