Какая скорость алгоритма итерации по массиву и возврата значения из него

На интервью лучше сразу развести три похожие операции. Так вы покажете, что понимаете вопрос, а не просто вспоминаете формулу.

Итерация по массиву это проход по элементам. Если элементов n, то вы делаете до n шагов. Поэтому цикл, forEach, map, filter и reduce обычно оценивают как O(n).

Доступ по индексу это другая операция. Когда индекс уже известен, например items[3], движку не нужно проверять элементы с начала массива. В модели Big O такой доступ обычно считают O(1).

Поиск значения это третий случай. Если вы не знаете индекс и ищете элемент по условию, массив обычно придется просматривать по порядку. Поэтому find, findIndex, includes и indexOf в худшем случае O(n).

Хороший короткий ответ может звучать так:

Итерация по массиву занимает O(n), потому что мы обрабатываем каждый элемент. Возврат по известному индексу, например arr[i], обычно O(1). Но если под возвратом значения имеется в виду поиск элемента по значению или по id, это уже линейный поиск O(n), пока мы не используем другую структуру данных или специальный алгоритм.

Это безопасная формулировка. Вы сразу уточняете, что значит слово "возврат". На интервью это важно. Один и тот же вопрос может означать доступ к позиции или поиск нужного значения.

В этом примере три операции выглядят похожими, но имеют разную стоимость.

const users = [
  { id: 1, name: "Anna" },
  { id: 2, name: "Max" },
  { id: 3, name: "Sam" },
];

const secondUser = users[1];
// O(1), индекс уже известен

const names = users.map((user) => user.name);
// O(n), нужно пройти по всем пользователям

const user = users.find((user) => user.id === 3);
// O(n), индекс неизвестен, ищем по условию

Практический вывод простой. Если код стоит в обработчике редкого клика и список маленький, линейный поиск часто нормален. Если такой поиск выполняется на каждый ввод символа, на каждый рендер или для каждой строки таблицы, пользователь может заметить задержку.

Не нужно механически заменять все массивы на Map. Массив удобен, когда важен порядок, нужно рендерить список или данных мало. Map и Set полезнее, когда основная операция это повторный lookup по ключу или проверка наличия.

Стоимость подготовки тоже важна. Создание new Map(items.map(...)) занимает O(n). Это выгодно, если потом вы много раз ищете элементы по ключу. Для одного поиска это часто лишняя работа и лишняя память.

Плохой пример: для каждой строки списка мы линейно ищем связанную запись в другом массиве.

function UserList({ users, teams }) {
  return users.map((user) => {
    const team = teams.find((team) => team.id === user.teamId);

    return <UserRow key={user.id} user={user} team={team} />;
  });
}

Если пользователей n, а команд m, такой рендер может стать O(n * m). Для маленьких списков это не проблема. Но на больших таблицах или частых обновлениях интерфейс начнет тормозить. Ввод станет менее отзывчивым, скролл может дергаться, а каждый новый рендер будет повторять ту же дорогую работу.

Более безопасный вариант: подготовить индекс по id и использовать быстрый lookup.

import { useMemo } from "react";

function UserList({ users, teams }) {
  const teamById = useMemo(() => {
    return new Map(teams.map((team) => [team.id, team]));
  }, [teams]);

  return users.map((user) => {
    const team = teamById.get(user.teamId);

    return <UserRow key={user.id} user={user} team={team} />;
  });
}

Здесь подготовка индекса стоит O(m), а lookup для каждой строки обычно O(1). Важно следить за зависимостями useMemo, иначе можно получить устаревшие данные.

Если массив отсортирован, можно вспомнить бинарный поиск. Его сложность O(log n), потому что на каждом шаге отбрасывается половина диапазона. Но это работает только если порядок данных действительно гарантирован.

Обычные includes и indexOf не используют бинарный поиск автоматически. Если хотите O(log n), нужен свой бинарный поиск или библиотечная функция, которая явно работает с отсортированными данными.

Для ответа на интервью достаточно уверенно сказать так. Проход по массиву O(n), доступ по индексу O(1), поиск значения в массиве O(n). Затем добавьте практический вывод. В UI опасны не разовые маленькие операции, а повторные линейные поиски в горячем пути.

Сильный ответ показывает, что вы не просто знаете обозначения Big O, а умеете выбирать структуру данных под задачу. Если нужно рендерить список по порядку, массив подходит. Если нужно часто проверять наличие id, подумайте о Set. Если нужно быстро доставать сущность по id, подумайте о Map. Если данные отсортированы и поисков много, можно рассмотреть бинарный поиск.