2.4 Алгоритмы и структуры данных

1. Оцените алгоритмическую сложность следующей функции для складывания значений из объекта в массив в мире, где нет Object.values():

function getValues(object) {
  return Object.keys(object).reduce((arr, key) => [...arr, key], []);
}

O(n²).

O(1).

O(n).

2. А за сколько отработал бы встроенный Object.values()?

O(1).

O(n).

3. Насколько сложна эта функция «разворота» массива?

function reverse(array) {
  const reversed = [];

  for (let i = array.length - 1; i >= 0; i--) {
    reversed.push(array[i]);
  }

  return reversed;
}

O(n).

O(n²).

4. А такая?

function reverse(array) {
  const reversed = [];

  array.forEach(element => reversed.unshift(element))

  return reversed;
}

O(n).

O(n²).

5. Какая сложность у такого избавления от дубликатов в массиве? (Код, видимо, писал Игорь из прошлого раздела...)

function reverse(array) {
  let unique;

  for (let i = 0; i < array.length; i++) {
    const index = array.indexOf(element);

    if (index === i) {
      unique.unshift(element);
    }
  }

  unique.reverse();

  return unique;
}

O(n³).

O(n²).

O(n).

6. С помощью какой или каких структур данных можно сделать это быстрее всего?

Set.

Map.

Стек.

2.4. Снова оцениваем сложности функций