Большой О Упрощенный

Очень простое объяснение любимой буквы каждого программиста

Читая статьи, академические или другие, о компьютерном программировании и веб-разработке, вы, возможно, наткнулись на нечто, называемое нотацией Big O. Так что же это за таинственная нотация и почему вас это должно волновать?

Первое, что я делаю, когда запутался в новой теме, — захожу в Википедию. Посмотрим, что они скажут по этому поводу.

Большая нотация О — это математическая нотация, описывающая предельное поведение функции, когда аргумент стремится к определенному значению или бесконечности….

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

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

Постоянная сложность — O(1)

Самый простой из этих примеров для объяснения — постоянная сложность. Функцию можно описать как функцию постоянной сложности, если ее выполнение занимает одинаковое время, несмотря на размер набора данных. Примером этого может быть получение элемента из массива, где вы знаете индекс элемента. Программа точно знает, где найти то, что вы ищете, и поэтому не требует слишком много времени или слишком много операций для получения результата.

const arr = [1,2,3,4,5,6,7,8,9,0]
arr[4]
getItemFromArr = (index) => {
 return arr[index]
}
getItemFromArr(4)
// => 4

Линейная сложность — O (n)

При линейной сложности производительность зависит от размера набора данных. В этом примере вам потребуется n операций, чтобы найти искомый элемент. В то время как для небольшого набора данных проблемы с производительностью не будут иметь большого значения, для большого набора данных, содержащего тысячи элементов, вы, вероятно, захотите решить эту проблему. В худшем случае для выполнения задачи требуется n операций. Если у вас есть 10 предметов, то это не так уж и плохо. Но если у вас есть набор данных с 1 000 000 элементов, вы можете пересмотреть свой алгоритм и подойти к проблеме, чтобы увидеть, есть ли алгоритм с более высокой производительностью.

let sortedArr = [ 2, 4, 5, 6, 8, 10, 16, 32 ]
function linearSearch(num){
    sortedArr.forEach(function(item, index){
    if(item === num){
      console.log(`I found ${item} at index ${index}!`)
      return
    }
  })
}
linearSearch(32)
// logs "I found 32 at index 7!"

Квадратичная сложность — O (n²)

Квадратичная сложность — это квадрат (или куб, или любая другая степень) размера набора данных. Это видно в алгоритмах, которые имеют вложенные итерации. Таким образом, вопросы производительности важнее учитывать. Например, в нашем последнем примере наихудшим сценарием для набора данных с 1 000 000 будет 1 000 000 операций, чтобы найти элемент, который вы ищете. Для алгоритма с квадратичной сложностью, такого как в приведенном ниже примере, потребуется 1 000 000² или 1 000 000 000 000 операций в худшем случае, чтобы найти элемент.

const arr1 = [21, 80, 4, 69, 23, 35]
const arr2 = [0, 9, 8, 7, 6, 5, 4, 3, 2, 1]
let findFirstMatch = () => {
  for(let i = 0; i < arr1.length; i++){
    for(let j = 0; j < arr2.length; j++){
      if(arr1[i] === arr2[j]){
        return `Found A Match: Number ${arr1[i]} at index ${i} in arr1 and index ${j} in arr2.`
      }
    }
  }
}
findFirstMatch()
// => 'Found A Match: Number 4 at index 2 in arr1 and index 6 in arr2.'

Логарифмическая сложность — O (log n)

Логарифмическая сложность будет принимать log 2 n любого количества элементов в наборе данных. В информатике мы используем логарифм с основанием 2. Для тех из вас, кто давно не посещал уроки математики, логарифмы — это обратные уравнения экспоненциальных уравнений. Это означает, что log2 64 является обратным 2⁶, а это означает, что log2 64 = 6, а 2⁶ = 64. Таким образом, при log n времени (предполагается, что 2 присутствует в качестве основания), это занимает около log n раз. завершить алгоритм в худшем случае. Логарифмическая сложность используется в бинарном поиске, о котором подробнее можно прочитать здесь. Если у нас есть массив с 13 элементами, как показано ниже, потребуется лог 13, или около 3,7 попыток найти искомый элемент. Преимущества этого по сравнению с линейной сложностью легко увидеть, когда мы используем пример с большим набором данных. Как мы видели ранее, если бы у нас был набор данных с 1 000 000 элементов, наихудшим сценарием для линейной сложности было бы 1 000 000 шагов. Log 1 000 000 сокращает этот процесс примерно до 19 шагов.

let orderedList = [ 2, 3, 5, 7, 8, 10, 12, 15, 18, 19, 24, 87, 111 ];
function binarySearch(arr, num) {
  
  let lowestNum = 0;
  let highestNum = orderedList.length - 1;
  let midPoint;
  let checkMidpoint;
 
 while(lowestNum <= highestNum) {
    midPoint = Math.floor((lowestNum + highestNum) / 2),
    // midPoint = arr.length/2
     checkMidpoint = arr[midPoint];
if(checkMidpoint === num) {
                console.log('I found the number you were looking for at index: ' + midPoint + '! The value is ' + checkMidpoint + "!");
      return;
     }
     if(num < checkMidpoint) {
         highestNum = midPoint - 1;
            } 
     else {
         lowestNum = midPoint + 1;
     }
        }
 
 return `I couldn't find ${num} in the list.` ;
}
binarySearch(orderedList,10);
// => I found the number you were looking for at index: 5! The value is 10!

Резюме

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

Источники