Blazkowiczno56892Правильно сделать так?
Да: http://stackoverflow.com/a/8923300
Простите как же да, если getEntry (и containsKey соответственно) это O(n) (в худшем случае).
Другими словами
for(int element : ArrayP) if(map1.contains(element)) map2.add(element);
Это O(n*p).
А O(n+p) это может быть только при условии, что количество корзин в hashmap больше n и p и нет коллизий.

BlazkowiczСергей АрсеньевПростите как же да, если getEntry (и containsKey соответственно) это O(n) (в худшем случае).

А почему обязательно "худший случай рассматривать". При нормальной реализации hashCode - O(1) о чем и заявлено в JavaDoc.

Ну на заборе тоже пишут. От


Никуда не уйти.

А в академичиских задачах рассматривают именно худший случай. Ибо "наиболее часто встречающийся случай" всего лишь зависит от выборки, а никак не от генеральной совокупности.
Подгонка hash функции под отсутствие коллизий съест свою сложность.

P.S. Принцип то конечно тот же, но задача решается несколько проще например для 32 int достаточно гигабайтика оперативочки и трех пробежек по массивам.

Blazkowicz,

Нет это сокральное знание передают только устно. :)

O(1) там накроется уже на добавлении с rehash. Чтобы обезапастся от него надо установить initial capacity и load factor
http://docs.oracle.com/javase/7/docs/api/java/util/HashMap.html If the initial capacity is greater than the maximum number of entries divided by the load factor, no rehash operations will ever occur.
(В нашем случае это проделано небыло)
Но там жеThis implementation provides constant-time performance for the basic operations (get and put), assuming the hash function disperses the elements properly among the buckets. Iteration over collection views requires time proportional to the "capacity" of the HashMap instance (the number of buckets) plus its size (the number of key-value mappings). Thus, it's very important not to set the initial capacity too high (or the load factor too low) if iteration performance is important.
Т.е. если мы сделаем их зависимыми от n то не видать нам O(n), а если не сделаем то может проскочит, а может и нет.

Alexey TominПочинили в 8ке, по т.к. это security, то в 7ку включили (просто Сергей 7ку не видит давно). 6ка- всё...

Г.м. кто просвятит каким алгоритмом можно "построить бинарное дерево" (см выше названный ютюб в вышеназванное время) за O(1)?

no56892Всем спасибо за ответы, а по поводу как с делать O(n+p+q) и в худшем случае - это подойдет только для целых чисел размером <= int
Теоретически для чего угодно (что может быть выражено фиксированным количеством бит) за четверть адресуемой этим количеством бит памяти (за исключением очень маленьких - так для массивов boolean нужно 4 бита).