1. Последовательность Фибоначчи:
function fibonacci(n) {
  if (n === 0) {
    return 0;
  } else if (n === 1) {
    return 1;
  } else {
    return fibonacci(n - 1) + fibonacci(n - 2); //function recursively calls itself twice for each value of n.
  }
}

Временная сложность: O(2^n), поскольку функция рекурсивно вызывает себя дважды для каждого значения n.
Пространственная сложность: O(n ), каждому рекурсивному вызову требуется память для хранения своего состояния в стеке вызовов.

2. Перевернуть строку

function reverseString(str) {
  return str.split('').reverse().join(''); // t(n) = O(n)+O(n)+O(n)
}

Временная сложность: O(n), так как функция должна перебирать каждый символ в строке. Функция split разбивает строку на массив отдельных символов, что занимает O(n) времени. Затем функция reverse меняет порядок символов в массиве на обратный, что также занимает время O(n). Наконец, функция join соединяет перевернутый массив обратно в строку, что занимает O(n) времени.
Пространственная сложность: O(n), поскольку Функция создает массив из n элементов.

3. Пузырьковая сортировка:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {          // O(n)
    for (let j = 0; j < arr.length - 1; j++) {    // O(n)
      if (arr[j] > arr[j + 1]) {
        let temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
  return arr;
}

Временная сложность: O(n²), поскольку функция перебирает каждую пару элементов в массиве.
Пространственная сложность: O(1), так как функция сортирует массив на месте.

4. Двоичный поиск. Это широко используемый алгоритм поиска определенного значения в отсортированном массиве.

function binarySearch(arr, val) {
  let start = 0;
  let end = arr.length - 1;
  while (start <= end) {
    let mid = Math.floor((start + end) / 2);
    if (arr[mid] === val) {
      return mid;
    } else if (arr[mid] < val) {
      start = mid + 1;
    } else {
      end = mid - 1;
    }
  }
  return -1;
}

Временная сложность:
- В худшем случае: O(log n)
- В лучшем случае: O(1)
- Средний случай: O(log n)
В худшем случае бинарный поиск требует O(log n) сравнений, чтобы найти целевой элемент, где n количество элементов в отсортированном массиве. В лучшем случае целевой элемент находится при первом сравнении, что приводит к временной сложности O(1). Однако в среднем алгоритму требуется O(log n) сравнений, чтобы найти целевой элемент.
Пространственная сложность: O(1), поскольку функция сортирует массив на месте.

5. Найти длину самой длинной подстроки без повторяющихся символов

function lengthOfLongestSubstring(str) {
  let left = 0;
  let maxLength = 0;
  const charSet = new Set();
  
  for (let right = 0; right < str.length; right++) {
    while (charSet.has(str[right])) {
      charSet.delete(str[left]);
      left++;
    }
    charSet.add(str[right]);
    maxLength = Math.max(maxLength, right - left + 1);
  }
  
  return maxLength;
}

Временная сложность: O(n),алгоритм перебирает входную строку str один раз, а временная сложность однократного перебора строки составляет O(n), где n это длина строки. Цикл while внутри цикла for будет выполняться не более n раз, так как каждый символ в строке обрабатывается ровно один раз. Таким образом, общая временная сложность алгоритма составляет O(n).
Пространственная сложность: O(min(k)),алгоритм использует набор charSet для отслеживания уникальных символов в текущей подстроке. Набор может хранить не более k уникальных символов в любой момент времени, где k — длина самой длинной подстроки без повторяющихся символов. Следовательно, пространственная сложность алгоритма равна O(k).

Спасибо, что нашли время, чтобы прочитать мою статью. Надеюсь, вы нашли его информативным и наводящим на размышления. Если у вас есть какие-либо вопросы или комментарии, пожалуйста, не стесняйтесь оставлять их ниже. Ваши отзывы всегда ценятся. 😃