Практика

Вам необходимо установить время за которое выполнится алгоритм.

function findMinimum(arr) {
  let min = arr[0];
  for (let i = 1; i < arr.length; i++) {
    if (arr[i] < min) {
      min = arr[i];
    }
  }
  return min;
}

Показать ответ

Общая временная сложность функции складывается из сложностей всех её частей: (1) + O(n) + O(1) = O(n)

function containsElement(arr, num) {
  for (let i = 0; i < arr.length; i++) {
    if (arr[i] === num) {
      return true;
    }
  }
  return false;
}

Показать ответ

Временная сложность функции O(n)

function removeDuplicates(arr) {
  const uniqueElements = new Set();
  for (let i = 0; i < arr.length; i++) {
    uniqueElements.add(arr[i]);
  }
  return Array.from(uniqueElements);
}

Показать ответ

Общая временная сложность функции складывается из сложностей всех её частей: O(1)+O(n)+O(n)=O(n)

function mergeSortedArrays(arr1, arr2) {
  const result = [];
  let i = 0,
    j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] < arr2[j]) {
      result.push(arr1[i++]);
    } else {
      result.push(arr2[j++]);
    }
  }
  while (i < arr1.length) {
    result.push(arr1[i++]);
  }
  while (j < arr2.length) {
    result.push(arr2[j++]);
  }
  return result;
}

Показать ответ

Общая временная сложность функции складывается из сложностей всех её частей: O(1)+O(n+m)+O(n+m)=O(n+m)

function findAllSubstrings(str) {
  const substrings = new Set();
  for (let i = 0; i < str.length; i++) {
    for (let j = i + 1; j <= str.length; j++) {
      substrings.add(str.substring(i, j));
    }
  }
  return Array.from(substrings);
}

Показать ответ

Общая временная сложность функции складывается из сложностей всех её частей: O(n)×O(n/2)×O(n)=O(n^3)

function smaller(arr) {
  const newArr = [];
  let num = 0;

  for (let i = 0, j = i + 1; i < arr.length && j < arr.length; ) {
    if (arr[i] > arr[j]) num++;
    j++;

    if (j === arr.length) {
      i++;
      j = i + 1;
      newArr.push(num);
      num = 0;
    }
  }

  newArr.push(num);
  return newArr;
}

Показать ответ

Общая временная сложность функции складывается из сложностей всех её частей: O(n)×O(n−i)=O(n)×O(n)=O(n^2)

function mergeSort(arr) {
  if (arr.length < 2) {
    return arr;
  }
  const middle = Math.floor(arr.length / 2);
  const left = arr.slice(0, middle);
  const right = arr.slice(middle);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];
  let leftIndex = 0;
  let rightIndex = 0;

  while (leftIndex < left.length && rightIndex < right.length) {
    if (left[leftIndex] < right[rightIndex]) {
      result.push(left[leftIndex]);
      leftIndex++;
    } else {
      result.push(right[rightIndex]);
      rightIndex++;
    }
  }

  return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

Показать ответ

Общая временная сложность функции составляет O(n * log n)