|
|
|
Сложность добавления p элементов в конец ArrayList размера n
|
|||
|---|---|---|---|
|
#18+
в тесте встретил вопрос: авторAdding p elements to the end of an ArrayList (of size n) is говорят, что правильный ответ O(p) авторExplanation Adding an element to the end of an ArrayList is a constant time operation, unless the backing array is full and must be replaced by a larger array. In that case, a new array is constructed, whose length (in Java 8) is 1.5 times the length of the old array. Then all the elements are copied from the old array to the new array. This longer copy operation is thus amortized over the p element additions. я чего-то не понял. Можете разъяснить? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.11.2015, 17:29 |
|
||
|
Сложность добавления p элементов в конец ArrayList размера n
|
|||
|---|---|---|---|
|
#18+
или тут имеется ввиду положительный сценарий, что p влезут в текущее capacity и массив не придётся расширять? ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.11.2015, 17:38 |
|
||
|
Сложность добавления p элементов в конец ArrayList размера n
|
|||
|---|---|---|---|
|
#18+
redwhite90, Да, потому что в случае нужды ты всегда можешь задать capacity достаточный для большинства сценариев и всё ещё эффективный по памяти. ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.11.2015, 18:52 |
|
||
|
Сложность добавления p элементов в конец ArrayList размера n
|
|||
|---|---|---|---|
|
#18+
Строго говоря, сложность при больших p и n равна O((p+n)*log 1.5 (p)), если добавлять по 1 элементу, с автоматическим увеличением размера массива. Это в соответствии с приведенным Explanation. Но можно предварительно выполнить Код: java 1. , и тогда сложность сводится к O(n+p) ... |
|||
|
:
Нравится:
Не нравится:
|
|||
| 13.11.2015, 20:05 |
|
||
|
|

start [/forum/topic.php?fid=59&msg=39103243&tid=2124676]: |
0ms |
get settings: |
10ms |
get forum list: |
19ms |
check forum access: |
4ms |
check topic access: |
4ms |
track hit: |
48ms |
get topic data: |
13ms |
get forum data: |
3ms |
get page messages: |
52ms |
get tp. blocked users: |
2ms |
| others: | 246ms |
| total: | 401ms |

| 0 / 0 |
