Flashcards
Arraylist sizing
Flashcards do conjunto (1)
- 1ArrayList doubles capacity when it is full. Isn't that wasteful?As we insert elements, we double the capacity when the size of the array is a power of 2. 50 after X elements,
we double the capacity at array sizes 1, 2, 4, 8, 16, ... , X.
That doubling takes, respectively, 1, 2, 4, 8, 16, 32,
64, ... , X copies.
What is the sum of 1 + 2 + 4 + 8 + 16 + ... + X? If you read this sum left to right, it starts with 1 and doubles
until it gets to X. If you read right to left, it starts with X and halves until it gets to 1.
What then is the sum of X + X + X + Ys + ... + 1? This is roughly 2X.
Therefore, X insertions take O( 2X) time. The amortized time for each insertion is O( 1)
Informações
- Descrição
- Data Structures (Amortized time) FlashCards sobre Arraylist sizing, criado por Rajaram Mallya em 05-07-2018.
- Criado por
- Rajaram Mallya
- Visualizações
- 0
- Avaliação