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 cards · basic cards · AI-written, checked twice. Edit anything.
- O que a notação Big O mede?
Show answer
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).
Show answer
Tempo constante; o tempo de execução não muda independentemente do tamanho da entrada.- Defina a complexidade de tempo O(n).
Show answer
Tempo linear; o tempo de execução cresce proporcionalmente ao tamanho da entrada n.- Defina a complexidade de tempo O(log n).
Show answer
Tempo logarítmico; o tempo de execução cresce com o logaritmo do tamanho da entrada.- Defina a complexidade de tempo O(n^2).
Show answer
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).
Show answer
Tempo linearítmico; o tempo de execução é n vezes o logaritmo de n.- Defina a complexidade de tempo O(2^n).
Show answer
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?
Show answer
O(1), tempo constante.- Qual é a complexidade de tempo de buscar um valor em um array não ordenado?
Show answer
O(n), tempo linear.- Qual é a complexidade de tempo da busca binária em um array ordenado?
Show answer
O(log n), tempo logarítmico.- O que deve ser verdade sobre um array antes de usar a busca binária?
Show answer
O array deve estar ordenado.- Qual é a complexidade de tempo de inserir um elemento no início de um array?
Show answer
O(n), tempo linear.- Qual é a complexidade de tempo de adicionar um elemento a um array dinâmico com capacidade disponível?
Show answer
O(1), tempo constante amortizado.- Qual é a complexidade de tempo média de buscar em uma tabela hash?
Show answer
O(1), tempo constante com uma boa função hash.- Qual é a complexidade de tempo do quicksort no caso médio?
Show answer
O(n log n), tempo linearítmico.
FlashKeepers