Сроки и сложность этого кода

Вопрос: this вопрос, а ниже - мой код.Сроки и сложность этого кода

import java.util.*; 

// you can write to stdout for debugging purposes, e.g. 
// System.out.println("this is a debug message"); 

class Solution { 
    public int solution(int[] A) { 
    Set <Integer> set = new HashSet<Integer>(); 
    for(int i=0;i<A.length;i++){ 
      set.add(A[i]); 
     } 
     return set.size(); 
     // write your code in Java SE 8 
    } 
}

У меня вопрос, какова временная сложность этого кода. Я предположил, что это O (n). n - количество элементов, но мои результаты теста говорят, что он обнаружил временную сложность O (n * log n). Не могли бы вы рассказать мне правильный ответ с кратким объяснением?

источник

2016-11-12 Saugat Awale

Для одного вы знаете 'A.length', но набор должен расти адаптивно, я бы предположил, что он удваивает емкость (или аналогичную экспоненту), копируя элементы (возможно, даже переделывая их), что приводит к некоторому' n * log n' операций. Попробуйте инициализировать набор правильно, используя ['HashSet (int, float)'] (https://docs.oracle.com/javase/7/docs/api/java/util/HashSet.html#HashSet (int,% 20float)) и посмотрите, не изменилось ли это поведение. Будьте консервативны относительно начальной емкости, выберите емкость больше, чем 'A.length'. – BeyelerStudios

ожидается, амортизируется стоимость вставки в HashMap в Java представляет собой О (1). Это означает, что если вы сделаете серию n вставок в HashMap, то в среднем время выполнения будет O (n) при условии, что у вас хорошая хэш-функция. Часть «в среднем» относится к тому факту, что существует некоторая неотъемлемая случайность в отношении того, как распределяются объекты, а это значит, что возможно, что это может занять больше времени. «Лучший» способ характеризовать среду выполнения «ожидался O (n)», но с пониманием, что если вы действительно поистине не повезет, это может быть дольше, чем это.

источник

2016-11-15 00:55:37 templatetypedef

Сроки и сложность этого кода

ответ

Смежные вопросы