Notação Big O, algoritmos comuns de ordenação e busca, e padrões de recursão cobrados em entrevistas técnicas e disciplinas universitárias.
38 cartas · cartas básicas · Escrito por IA, verificado duas vezes. Edite à vontade.
- O que a notação Big O mede?
- Como o tempo de execução ou os requisitos de espaço de um algoritmo crescem à medida que o tamanho da entrada aumenta.
- Defina a complexidade de tempo O(1).
- Tempo constante; o tempo de execução não muda independentemente do tamanho da entrada.
- Defina a complexidade de tempo O(n).
- Tempo linear; o tempo de execução cresce proporcionalmente ao tamanho da entrada n.
- Defina a complexidade de tempo O(log n).
- Tempo logarítmico; o tempo de execução cresce com o logaritmo do tamanho da entrada.
- Defina a complexidade de tempo O(n^2).
- Tempo quadrático; o tempo de execução cresce com o quadrado do tamanho da entrada.
- Defina a complexidade de tempo O(n log n).
- Tempo linearítmico; o tempo de execução é n vezes o logaritmo de n.
- Defina a complexidade de tempo O(2^n).
- Tempo exponencial; o tempo de execução dobra a cada aumento no tamanho da entrada.
- Qual é a complexidade de tempo de acessar um elemento de um array pelo índice?
- O(1), tempo constante.
- Qual é a complexidade de tempo de buscar um valor em um array não ordenado?
- O(n), tempo linear.
- Qual é a complexidade de tempo da busca binária em um array ordenado?
- O(log n), tempo logarítmico.
- O que deve ser verdade sobre um array antes de usar a busca binária?
- O array deve estar ordenado.
- Qual é a complexidade de tempo de inserir um elemento no início de um array?
- O(n), tempo linear.
- Qual é a complexidade de tempo de adicionar um elemento a um array dinâmico com capacidade disponível?
- O(1), tempo constante amortizado.
- Qual é a complexidade de tempo média de buscar em uma tabela hash?
- O(1), tempo constante com uma boa função hash.
- Qual é a complexidade de tempo do quicksort no caso médio?
- O(n log n), tempo linearítmico.
FlashKeepers