Algoritmos e estruturas de dados · Estruturas de dados · 5 min de leitura
Arrays e strings
A estrutura mais básica: acesso por índice em O(1), mas inserir no meio desloca tudo. E por que concatenar strings num laço pode virar O(n²).
Arraste para o lado para ver o diagrama inteiro.
Memória contígua
Um array guarda os elementos lado a lado na memória. Por isso o endereço de a[i] é uma conta (início + i × tamanho) e o acesso é O(1). O preço: inserir ou remover no meio exige deslocar tudo o que vem depois — O(n).
Arrays dinâmicos
ArrayList/MutableList no Kotlin, Array no Swift e o array do JavaScript crescem sozinhos: quando enchem, alocam um bloco maior (em geral 1,5× ou 2×) e copiam. Uma cópia custa O(n), mas acontece tão raramente que adicionar no fim sai O(1) amortizado.
Strings imutáveis
Em Kotlin/Java e Swift, cada s += x pode criar uma string nova e copiar a antiga. Num laço de n voltas isso soma 1 + 2 + … + n cópias = O(n²). Use buildString/StringBuilder, joinToString ou, em TypeScript, array.join("").
No código: antes e depois
fun csv(linhas: List<String>): String {
var s = ""
for (l in linhas) s += l + "\n" // copia tudo a cada volta
return s
}fun csv(linhas: List<String>): String = buildString {
for (l in linhas) append(l).append('\n') // um buffer só, O(n)
}
// ou, mais curto: linhas.joinToString("\n", postfix = "\n")buildString usa um StringBuilder por baixo: cresce como um array dinâmico e copia cada caractere poucas vezes.
Em resumo
- Acesso por índice: O(1).
- Inserir ou remover no meio: O(n).
- Adicionar no fim de array dinâmico: O(1) amortizado.
- Concatenar strings em laço pode ser O(n²); use um builder.
Exercícios
Responda e confira na hora. Complexidades valem com ou sem espaços, como O(n log n).
-
Qual a complexidade de ler o elemento de índice i de um array?
Ver a solução
Resposta: O(1). O endereço é calculado com uma conta (início + i × tamanho), independente de n.
-
Qual a complexidade de inserir no início de um array com n elementos?
Ver a solução
Resposta: O(n). Todos os n elementos precisam andar uma posição para abrir espaço.
-
Num laço de 100 voltas, cada s += "x" copia a string inteira: 1 caractere na 1ª volta, 2 na 2ª, …, 100 na 100ª. Quantos caracteres são copiados no total?
Ver a solução
Resposta: 5050. 1 + 2 + … + n = n(n + 1)/2 = 100 × 101 / 2 = 5050 — cresce como n², por isso O(n²).
Perguntar à IA
Monte um prompt pronto sobre Arrays e strings na sua linguagem e no seu caso, e abra num chat gratuito.
O prompt vai para o site que você escolher. Não cole senhas, tokens nem dados reais de clientes. Para Gemini e outros, copie e cole.