Я полнофункциональный разработчик, которому нравится писать о технологиях (среди прочего - если эта статья интересует / помогает вам подписаться на меня на Medium и Twitter, чтобы получить больше подобного контента.

Проблема поиска пиков - зачем это нужно?

Хотя это немного игрушечная проблема, задача поиска пиков - отличная платформа, чтобы начать разбираться с некоторыми из основных концепций алгоритмического мышления. Он служит отличным введением в ответ на вопросы о том, как эффективно решать проблемы с большими объемами данных.

Зачем беспокоиться об алгоритмической эффективности?

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

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

Рассмотрим два алгоритма, один из которых имеет «линейную временную сложность», что означает, что время, необходимое для завершения выполнения, увеличивается пропорционально размеру набора данных. Здесь для обработки набора данных, который увеличивается в три раза, потребуется в три раза больше времени. Другой имеет «кубическую временную сложность», что означает, что если мы увеличим размер набора данных в 3 раза, выполнение нашей программы займет в 27 раз больше времени.

Учитывая размер наборов данных в современном мире (где Facebook имеет данные о более чем 2 миллиардах пользователей, а компьютеры настроены на анализ человеческого генома, который имеет более 3 миллиардов пар оснований для просеивания), становится ясно, что есть огромная ценность в обучении оптимизации наших процедур - с такими большими наборами данных алгоритмическая эффективность иногда может иметь значение, оказывая услугу, или не предоставляя вообще ничего.

Поиск пиков в одном измерении

Взгляните на следующий вопрос:

[a,b,c,d,e,f,g,h,i]

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

a является пиком, если a ≥ b - поскольку у него только один сосед.

b является пиком тогда и только тогда, когда b≥a и b≥c

Напишите алгоритм, который находит пик (если пик существует)

Наивное решение

На первый взгляд, это выглядит тривиальной проблемой, решение которой - «посмотрите направо, затем посмотрите налево». Если вы равны своим соседям или выше их, вы - вершина ». Кроме того, в этом случае нам не нужно учитывать возможность отсутствия пика. Либо весь набор состоит из пиков (поскольку все числа одинаковы), либо есть хотя бы одно число, которое выше своих соседей.

Напишем этот пример в коде JavaScript:

function peak_finder(array){
  let counter = 0
  let peak = 0
  let peak_index =0
  while (counter <= array.length){
    console.log(counter)
  if (counter === 0){
    if (a[0]>=a[1]){
      peak = a[0]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter+=1
    }
  }else if(counter === array.length-1){
     if (a[array.length-1] >= a[array.length-2]){
     peak = a[array.length-1]
     peak_index = counter
     counter = array.length
     return `The ${counter-1} indexed number, ${peak} is a peak`
     }
   }else{
      if (a[counter]> a[counter+1] && a[counter]> a[counter-1]){
      peak = a[counter]
      peak_index = counter
      counter = array.length
      return `The ${counter-1} indexed number, ${peak} is a peak`
    }else{
      counter += 1
    }
  }
}
}

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

Насколько эффективен этот метод?

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

Для больших наборов данных это может быть меньше идеального. Есть ли способ сделать что-нибудь лучше?

Лучшее решение: алгоритм двоичного поиска

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

function peak_finder2(array){
    if (array.length)=== 0{
       return  `Array cannot be empty`
     }else if (array.length === 1){
       return array[0]
     }else{
       let mid_index = Math.floor(array.length*0.5)
      if (array[mid_index +1]>array[mid_index]){
         return peak_finding(array.slice(mid_index + 1 ))
       }else if (array[mid_index -1]>array[mid_index]){ 
        new=array.reverse().slice(mid_index+1).reverse()
        return peak_finding(new)  
        }else{
         return array[mid_index]
        }
      }
}

Это лучший способ решить возникшую проблему. Давайте посмотрим, почему:

Время тренировки - сложность

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

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

Это меняет формулировку вопроса на сколько раз мы можем половину массива длиной N, прежде чем у нас останется только один элемент?

В математических обозначениях наш вопрос выглядит так:

if 1 = N / (2ˣ) ,

Найдите x

Если вы проработаете проблему, вы придете к выводу, что

x = журнал ₂ (N)

Итак, теперь мы разработали количество вычислений для наихудшего случая - время для наихудшего случая будет кратно этому. Таким образом, наихудший случай временной сложности нашего алгоритма принадлежит классу O (K log ₂ (N)), где k - некоторая константа.

Давайте сравним наихудший случай временной сложности для обоих методов, которые мы придумали до сих пор, и почувствуем, насколько лучше этот метод работает по мере увеличения размера нашего ввода N:

По мере того, как N становится все больше и больше, этот алгоритм становится все более предпочтительным по сравнению с алгоритмом, который мы реализовали в начале этой статьи.