Какова временная сложность следующих операций: линейный поиск, суммирование элементов массива, бинарный поиск и поиск дубликатов вложенным циклом?

Временная сложность показывает, как растёт число операций алгоритма при увеличении размера входных данных n. В контексте массивов это ключевой инструмент для сравнения решений и выбора подходящего подхода на собеседовании и в реальной разработке.

Разбор каждой операции

• Линейный поиск — проходим по массиву слева направо, пока не найдём нужный элемент. В худшем случае (элемент в конце или отсутствует) выполняется n сравнений, поэтому сложность O(n).
• Суммирование элементов — один проход по массиву, на каждом шаге одно сложение. Итог: n операций, сложность O(n).
• Бинарный поиск — работает только на отсортированном массиве. На каждом шаге отбрасывается половина диапазона, поэтому число шагов примерно log₂(n). Сложность O(log n).
• Поиск дубликатов вложенным циклом — внешний цикл по i, внутренний по j > i. Число сравнений примерно n²/2, что асимптотически O(n²).

Пример кода

// O(n) — линейный поиск
function linearSearch(arr, target) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === target) return i;
  }
  return -1;
}

// O(n) — суммирование
function sum(arr) {
  let s = 0;
  for (const x of arr) s += x;
  return s;
}

// O(log n) — бинарный поиск (массив отсортирован)
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// O(n^2) — поиск дубликатов
function hasDuplicates(arr) {
  for (let i = 0; i < arr.length; i++)
    for (let j = i + 1; j < arr.length; j++)
      if (arr[i] === arr[j]) return true;
  return false;
}

Практические замечания

Бинарный поиск требует предварительной сортировки O(n log n), что оправдано при многократных поисках. Поиск дубликатов через Set или сортировку можно свести к O(n) или O(n log n) соответственно — это типичный вопрос на оптимизацию.

Итог: линейные проходы дают O(n), бинарный поиск — O(log n) на отсортированных данных, а вложенные циклы — O(n²); выбирайте структуру данных и алгоритм исходя из требуемой асимптотики.