The Last Algorithms Course You'll Need

Question 1

What is the Big O notation?

Answer 1

Big O is a way to categorize your algorithms time or memory requirements based on input. It is meant to generalize the growth of the algorithm.

As your input grows, Big O tells how fast the computation or memory grow.

Question 2

What’s the importance of the Big O notation?

Answer 2

Often it will help us make decisions about what data structures and algorithms to use. Knowing how they will perform can greatly help create the best possible program out there.

Question 3

What’s the time complexity of this algorithm?

function sum_char_codes(n: string): number {
    let sum = 0;
    for (let i = 0; i < n.length; i++) {
        sum += n.charCodeAt(i)
    }

    return sum;
}

Answer 3

O(n)

The time complexity grows linearly as the input “n” grows.

Question 4

Suponha que você tenha uma lista em ordem alfabética com 128 nomes e esteja fazendo uma pesquisa binária. Qual seria o número máximo de etapas que você levaria para encontrar o nome desejado?

Answer 4

2^n = 128

n = 7

O máximo de etapas que levaria para encontrar o nome desejado é 7

Question 5

Ordene os tempos de execução do mais rápido para o mais lento:

O(n)
O(n!)
O(n log n)
O(log n)
O(2^n)
O(1)
O(n²)

Answer 5

O(1)
O(log n)
O(n)
O(n log n)
O(n²)
O(2^n)
O(n!)

Question 6

Qual o tempo de execução de uma busca binária em notação Big O?

Answer 6

O(log n)

Exemplo:
O(log 128 na base 2) = 7

Ou seja, “n” é o tamanho da entrada, o algoritmo de busca binária precisa de 7 iterações no pior caso para encontrar o valor desejado. 2^7 é igual a 128.

Question 7

Qual a complexidade de tempo para acessar um elemento qualquer de um array?

Answer 7

O(1)

Question 8

Em qual situação é mais recomendado utilizar um array? E uma lista encadeada?

Answer 8

Se você precisa frequentemente acessar os elementos de uma coleção, um array é ideal. Pois sua complexidade de acesso é O(1). Enquanto a inserção tem complexidade O(n).

A lista encadeada é mais recomendada em casos que existem muitas inserções ou remoções da coleção.
Operações de inserção e remoção em uma lista encadeada podem ser realizadas em tempo constante O(1), desde que você tenha o ponteiro para a posição correta. Enquanto que a sua complexidade para acessar elementos é de O(n).