что такое временная сложность и вспомогательное пространство для этого метода?

Question

Какова сложность времени и вспомогательное пространство для этого метода? Может кто-нибудь сказать, пожалуйста, объясните мне результаты?

public Set<T> findRepeatedValues(List<T> list){
    Set<T> set = new HashSet<>();
    Set<T> repeatedValues = new HashSet<>();
    for (T i: list) {
        if (!set.add(i)) {
            repeatedValues.add(i);
        }
    }
    return repeatedValues;
}

что случилось, если я протестировал свой код, как показано ниже?

@Test
public void findRepeatedStrings(){
    List<String> stringList = new ArrayList<String>(Arrays.asList("ali","mahdi","hadi","mahdi","mojtaba","mohammad","mojtaba"));
    RepeatedValues repeatedValues = new RepeatedValues();
    Set values = repeatedValues.findRepeatedValues(stringList);
    for (Object i :
            values) {
        System.out.println(i);
    }
}

Answer 1

Сложность

• Сложность времени составляет O (n)
• Пространственная сложность O (n)

Объяснение

public Set<T> findRepeatedValues(List<T> list){
    // both sets contains n elements: hence space complexity is O(n)
    Set<T> set = new HashSet<>();
    Set<T> repeatedValues = new HashSet<>();

    // iterate over list only once: hence time complexity is O(n)
    for (T i: list) {
        // HashSet add has O(1) time complexity
        if (!set.add(i)) {
            repeatedValues.add(i);
        }
    }

    return repeatedValues;
}

Тест

Ваш тест неверен. Вы должны проверить, что возвращаемое Set содержит необходимые данные. Холодно будет выглядеть:

public static void findRepeatedStrings() {
    List<String> list = Arrays.asList("ali", "mahdi", "hadi", "mahdi", "mojtaba", "mohammad", "mojtaba");
    Set<String> values = new RepeatedValues<String>().findRepeatedValues(list);

    MatcherAssert.assertThat(values, IsCollectionWithSize.hasSize(2));
    MatcherAssert.assertThat(values, IsIterableContainingInOrder.contains("mahdi", "mojtaba"));
}

Answer 2

Сложность времени

Временная сложность вашего кода будет O(n), , где n - количество элементов в list. Причина:

for (T i : list) { // iterates through all the 'n' elements
    if (!set.add(i)) {
        repeatedValues.add(i);
    }
}

Пространственная сложность

С другой стороны, поскольку вы используете Set для временного хранения значений, пространство, требуемое в худшем случае для используемого Set, будет равно:

Set<T> set = new HashSet<>(list.size()); // all elements are unique

Следовательно, пространственная сложность вашего решения также будет O(n). Конечно, n это значение, которое является размером списка. Если размер списка увеличивается, увеличивается и необходимое пространство.

выход

public void printRepeatedStrings(){
    List<String> stringList = Arrays.asList("ali","mahdi","hadi","mahdi","mojtaba","mohammad","mojtaba");
    RepeatedValues<String> repeatedValues = new RepeatedValues<>(); // type 'T' bound 
    repeatedValues.findRepeatedValues(stringList)
                  .forEach(System.out::println); // prints ["mahdi","mojtaba"]
}