Почему следующие два дублирующих алгоритма поиска имеют разную временную сложность?

Question

Я читал это question. Выбранный ответ содержит следующие два алгоритма. Я не мог понять, почему первая сложность времени - O (ln (n)). В худшем случае, если массив не содержит никаких дубликатов, он будет циклически n раз, а второй. Я ошибаюсь или что-то не хватает? Спасибо

1) быстрее (в пределе) способ

Вот подход, основанный хэш. Вы должны платить за автобоксинг, но это O (ln (n)) вместо O (n2). Предприимчивый душа бы найти примитивный ИНТ на основе хэш-набор (Apache или Google Collections имеет такую ​​вещь, мне кажется.)

boolean duplicates(final int[] zipcodelist) 
{ 
    Set<Integer> lump = new HashSet<Integer>(); 
    for (int i : zipcodelist) 
    { 
    if (lump.contains(i)) return true; 
    lump.add(i); 
    } 
    return false; 
} 

2) Поклон HuyLe

ответ

знакомства HuyLe для более или менее O (п) решение, которое я думаю, потребности пару из add'l шагов:

static boolean duplicates(final int[] zipcodelist) {  
    final int MAXZIP = 99999;  
    boolean[] bitmap = new boolean[MAXZIP+1];  
    java.util.Arrays.fill(bitmap, false);  

    for (int item : zipcodeList) 
     if (!bitmap[item]) bitmap[item] = true; 
     else return true;  
    } 

    return false; 
} 

Answer 1

Первое решением следовало ожидать сложность O (N), так как весь список почтового индекса должен быть пройден, и обработка каждый почтовый индекс представляет собой O (1) ожидаемую сложность времени.

Даже принимая во внимание, что включение в HashMap может вызвать повторный хэш, сложность по-прежнему O(1). Это немного нелогично, поскольку между Java HashMap и предположением в ссылке не существует никакой связи, но она показывает, что это возможно.

Из HashSet документации:

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

То же самое для второго решения, которое правильно анализируется: O (n).

(Только примечание не по теме, битСет быстрее, чем массив, как видно в исходном сообщении, поскольку 8 boolean s упакованы в 1 byte, который использует меньше памяти).