Какова пространственная сложность Map <Integer, List <String>>?

Question

Я пытаюсь вычислить сложность пространства моего кода в Java, и я использую только карты и список, но я не уверен, что это O(n^2) или O(n) и почему? ,

Map<Integer, List<String>> map = new HashMap<Integer, List<String>>(); 
List<String> list = new ArrayList<String>();; 
Map<String, Integer> map = new HashMap<String,Integer>() ; 

Обычно структура данных внутри другой структуры данных, как правило, O (n^2) справа?

благодаря

Answer 1

Было бы полезно, чтобы определить, что п есть, то относительно легко определить сложность пространства. Я определяю n как число строк, которые помещаются в HashMap. Я также предполагаю, что минимальный коэффициент нагрузки в хэш-таблице равен 0,5. Пусть я быть размером целое число, S быть максимальный размер строки, Н пространство используется один слот хеш-таблицы и L быть максимальная длина списка в хэш-таблицу.

Тогда для минимально заполненной хэш-таблицы будет п/л занятых слотов, каждый из которых имеет не более SL пространства плюс я для ключа, выделенного. Сам хэш-стол примет 2Hn/L пространство --- 2 связано с коэффициентом нагрузки. Таким образом, общая площадь будет [(SL + I + 2H)/L] n, которая равна O (n).