Задача № 5: оптимизировать алгоритм

Когда вы впервые учитесь программировать, самое важное - добиться от вашего решения желаемых результатов. Можете ли вы взять веревку и перевернуть ее? Можете ли вы найти элемент в массиве? Можете ли вы распечатать список вещей на консоли?

После того, как вы разберетесь с основами, нужно подумать еще о чем: сколько времени требуется для запуска вашего кода. Это важно при увеличении масштабов ваших проектов - в идеале вы хотите как можно быстрее возвращать информацию пользователям вашего приложения.

Нотация Big O - это способ описания времени выполнения кода (ознакомьтесь с этим, чтобы ознакомиться с кратким введением). Давайте сохраним это в уме и определим, является ли строка палиндромом. Начнем с наилучшего сценария:

function isPalindrome(string) {
    return string[0] === string[string.length-1]
}

Здесь вы проверяете только самые первые и самые последние буквы строки. Ваш алгоритм знает, куда идти каждый раз, и его выполнение занимает одинаковое количество времени, независимо от того, сколько букв в строке. Это пример кода, который выполняется во время O (1). Но у нас возникла проблема - что, если первая и последняя буквы совпадают, а следующие за ними - нет? Нам нужно будет просмотреть гораздо больше писем, чем только первое и последнее.

Давайте посмотрим на наше решение для наихудшего сценария:

function isPalindrome(string) {
   return string === string.split("").reverse().join("")
}

Хотя это проще всего записать и аргументировать, на самом деле под капотом происходит много всего:

1. Мы разбиваем строку на массив (используя что-то похожее на цикл for)
2. Мы меняем этот массив (изменяя индекс каждой буквы в массиве)
3. Превращаем преобразованный массив обратно в строку (используя другой цикл for)

Каждый из них требует времени и места для вычисления и увеличивает общее время выполнения.

Давайте посмотрим на наш лучший сценарий:

function isPalindrome(string) {
   let end = string.length-1
   for(let i = 0; i < string.length/2; i++) {
       if(string[i] !== string[end]) {
          return false
         }
       end--    
    }
    return true
}

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

Давайте рассмотрим еще один случай: определение того, является ли какая-либо подстрока в строке палиндромом. Итак, мы ожидаем, что ввод «hellomomworld» вернет истину, потому что «мама» - это палиндром. Но «желто-красный» вернет false.

function isAnywhere(string){
  if(isPalindrome(string)){
    return true
  } 
  
  for(let i = 0; i < string.length; i++){
    for(let j = string.length; j > 3; j--){
      if(string.substr(i, j-i).length > 2) {
        if(isPalindrome(string.substr(i, j-i))){
        return true
        } 
      }
    }
  }
  return false
}

Здесь мы берем строку и сначала вызываем функцию isPalindrome, которую мы написали ранее, чтобы проверить, является ли вся строка палиндромом. Если это так, мы можем немедленно вернуть true.

В случае с «адским миром» нам нужно будет погрузиться глубже. Вместо одного цикла for нам теперь нужны два цикла for. Первый цикл будет смотреть на первую букву, затем на следующую и так далее. Второй цикл начинается с последней буквы строки и продолжается в обратном направлении. Мы берем разделы (или подстроки) строки, вставляем их в isPalindrome и продолжаем искать, пока не найдем тот, который является палиндромом. Если их нет, мы вернем false после выхода из циклов. Я также добавил проверку, чтобы убедиться, что подстрока всегда состоит как минимум из 3 букв, потому что одна буква всегда будет равна самой себе.

Наихудший сценарий с этим решением состоит в том, что палиндром находится в конце строки, и наш первый цикл for должен проходить через каждый индекс. На этот раз сложность этого решения составляет O (n²). Если алгоритму требуется O (n) время для запуска одного цикла for, и мы добавляем дополнительный цикл for, который просматривает каждый индекс, это добавит время. Итак, решение с 3 вложенными циклами имеет потенциальную временную сложность O (n³), где n - размер входных данных и т. Д.

Спасибо, что прочитали, и вот несколько дополнительных ресурсов: