Как сравнить сложность двух методов в Java?

Question

Как я могу сравнить сложность этих двух методов O?

Вот первый способ:

protected static List<Integer> removeDuplicates1(List<Integer> source) { 
    List<Integer> tmp = new ArrayList<Integer>(); 
    for (Integer element : source) { 
     if (!tmp.contains(element)) { 
      tmp.add(element); 
     } 
    } 

    //Collections.sort(tmp); 
    return tmp; 
} 

И второй один:

protected static List<Integer> removeDuplicates2(List<Integer> source) { 
    return new ArrayList<Integer>(new HashSet<Integer>(source)); 
} 

UPD

Я не знаю, как вычислить сложность O обоих методов ,

UPD2

Хорошо, временная сложность первого метода является O(n^2), второй O(n). А как насчет использования памяти? Кто более жадный и почему?

Answer 1

Второй лучше O(n) сложность (O(n^2) для первого).

Для первых вы идете по списку в цикле (n) и для каждой операции запуска , который в свою очередь проходит через список TMP, чтобы найти, является ли элемент существует (еще один n).

Для второго метода операции добавления в Set постоянны, так что фактически только один n.

Answer 2

Второй метод работает лучше, поскольку его сложность O(n) в отличие от первого, где он работает в O(n^2).

Сложность второго решения в случае нотации Big O - это O (n), поскольку она проходит через список только один раз. В то время как в первом случае он сначала для циклов работает один раз, но внутренний содержит mehtod снова работает во временном списке. Таким образом, сложность в этом случае равна O (n^2).

Answer 3

Не пытайтесь делать это на Java, просто попробуйте сделать это в псевдокоде.

В первом вопросе у вас есть два списка целых чисел; два списка номеров. Если нет других правил, мы можем предположить, что оба списка имеют длину около n элементов.

Вы прокладываете путь через один из списков и делаете что-то для каждого числа в нем. Если n чисел, это n шагов. Для каждого из этих n шагов вы говорите: «У другого списка есть этот номер?»

Чтобы проверить, есть ли в списке номер, наихудший случай - это не значит, что вам нужно проверить каждый элемент в списке, чтобы узнать. Это также n шагов, если второй список может быть примерно таким же большим, как первый.

Составляя их вместе: Просматривая список из n элементов и делая n вещей по каждому предмету.

Дайте мне знать, что вы думаете, что подходит, и после этого я отредактирую этот ответ.

Для второго фрагмента кода разделите его.

Прежде всего, вы создаете HashSet, используя все элементы ввода. Сколько времени требуется, чтобы вставить один элемент в HashSet? Если вы вставляете n элементов, умножьте время на одну вставку на n.

Второе, что происходит, это новый ArrayList. Проверка API, чтобы быть уверенным в том, что он делает: http://docs.oracle.com/javase/7/docs/api/java/util/ArrayList.html#ArrayList(java.util.Collection)

Это создает ArrayList, используя все элементы коллекции HashSet. Сколько времени требуется, чтобы вставить в список массивов? Умножьте это на количество элементов (n), чтобы получить ответ.

Поскольку это происходит как отдельные шаги, это разные вещи. Какая бы ни была более высокая сложность большого О, является доминирующей, и вы можете игнорировать другую. Если они оба имеют одинаковую сложность с большими O, это ответ; вы можете его игнорировать, так как O (2n) имеет ту же сложность, что и O (n); константы (например, 2x) теряются.