- Последовательность Фибоначчи:
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).
Спасибо, что нашли время, чтобы прочитать мою статью. Надеюсь, вы нашли его информативным и наводящим на размышления. Если у вас есть какие-либо вопросы или комментарии, пожалуйста, не стесняйтесь оставлять их ниже. Ваши отзывы всегда ценятся. 😃