Красота структур данных и алгоритмов JavaScript — сложность времени и пространства

алгоритм
Красота структур данных и алгоритмов JavaScript — сложность времени и пространства

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

1. Что такое анализ сложности?

  1. Структуры данных и алгоритмическое решение — это «как заставить компьютеры решать задачи быстрее и занимать меньше места».

  2. Следовательно, необходимо оценивать производительность структур данных и алгоритмов с точки зрения времени выполнения и занимаемой площади.

  3. Две концепции временной сложности и пространственной сложности используются для описания проблемы производительности, и вместе они называются сложностью.

  4. Сложность описывает, как время выполнения (или площадь) алгоритма увеличивается с размером данных.

2. Зачем делать анализ сложности?

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

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

3. Как выполнить анализ сложности?

3.1 Обозначение большого O

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

3.2 Временная сложность

1) Определение

Временная сложность алгоритма, то есть измерение времени алгоритма.

Обозначение временной сложности Big OНа самом деле, он конкретно не представляет реальное время выполнения кода, но представляетТенденция времени выполнения кода с увеличением размера данных, так еще называютАсимптотическая временная сложность, именуемыйвременная сложность(асимптотическая временная сложность).

Пример 1:

function aFun() {
    console.log("Hello, World!");      //  需要执行 1 次
    return 0;       // 需要执行 1 次
}

Затем этот метод должен выполнить 2 операции.

Пример 2:

function bFun(n) {
    for(let i = 0; i < n; i++) {         // 需要执行 (n + 1) 次
        console.log("Hello, World!");      // 需要执行 n 次
    }
    return 0;       // 需要执行 1 次
}

Тогда этому методу нужно выполнить ( n + 1 + n + 1 ) = 2n +2 ​​операции.

Пример 3:

 function cal(n) {
   let sum = 0; // 1 次
   let i = 1; // 1 次
   let j = 1; // 1 次
   for (; i <= n; ++i) {  // n 次
     j = 1;  // n 次
     for (; j <= n; ++j) {  // n * n ，也即是  n平方次
       sum = sum +  i * j;  // n * n ，也即是  n平方次
     }
   }
 }

Обратите внимание, что это двухуровневый цикл for, поэтому второй уровень выполняет n * n = n.2время, а цикл здесь ++i, который отличается от i++ в примере 2, что является разницей между добавлением сначала и добавлением позже.

Затем этот метод нужно выполнить ( n2 + n2 + n + n + 1 + 1 +1 ) = 2n2+2н + 3.

2) Особенности

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

Следовательно, временная сложность примера 1 выше равна T(n) = O(1), временная сложность примера 2 равна T(n) = O(n), а временная сложность примера 3 равна T(n) = О (н2).

3.3 Анализ временной сложности

    1. Сосредоточьтесь только на той части кода, которая выполняет больше всего циклов.

Отдельный фрагмент кода смотрит на высокие частоты: например, петли.

function cal(n) { 
   let sum = 0;
   let i = 1;
   for (; i <= n; ++i) {
     sum = sum + i;
   }
   return sum;
 }

Наиболее часто выполняется цикл for и код внутри, который выполняется n раз, поэтому временная сложность равна O(n).

    1. Закон сложения: общая сложность равна сложности кода с наибольшей величиной

Многосегментный код является самым большим: например, в фрагменте кода есть один цикл и несколько циклов, затем возьмите сложность нескольких циклов.

function cal(n) {
   let sum_1 = 0;
   let p = 1;
   for (; p < 100; ++p) {
     sum_1 = sum_1 + p;
   }

   let sum_2 = 0;
   let q = 1;
   for (; q < n; ++q) {
     sum_2 = sum_2 + q;
   }
 
   let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= n; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
 
   return sum_1 + sum_2 + sum_3;
 }

Приведенный выше код разделен на три части: sum_1, sum_2 и sum_3 соответственно, в основном это циклическая часть.

Первая часть, чтобы найти sum_1, ясно, что она была выполнена 100 раз, независимо от размера n, это постоянное время выполнения, которое не может отражатьтенденция роста, поэтому временная сложность равна O(1).

Вторая и третья части, для sum_2 и sum_3, временная сложность связана с размером n, который равен O(n) и O(n соответственно).2).

Таким образом, при максимальном порядке трех фрагментов кода окончательная временная сложность приведенного выше примера составляет O(n2).

Точно так же, если есть 3 слоя циклов for, то временная сложность равна O(n3), 4 слоя — это O(n4).

так,Общая временная сложность равна временной сложности кода с наибольшей величиной.

    1. Правило умножения: сложность вложенных тегов равна произведению сложности вложенного внутреннего и внешнего кода.

Вложенный код для поиска продуктов: например, рекурсия, несколько циклов и т. д.

function cal(n) {
   let ret = 0; 
   let i = 1;
   for (; i < n; ++i) {
     ret = ret + f(i); // 重点为  f(i)
   } 
 } 
 
function f(n) {
  let sum = 0;
  let i = 1;
  for (; i < n; ++i) {
    sum = sum + i;
  } 
  return sum;
 }

Метод cal вызывает метод f внутри цикла, а метод f также имеет цикл внутри.

Таким образом, временная сложность всей функции cal() равна T(n) = T1(n) * T2(n) = O(n*n) = O(n2).

    1. Добавление нескольких шкал: например, метод имеет два параметра для управления количеством двух циклов, затем берется и добавляется сложность двух.
function cal(m, n) {
  let sum_1 = 0;
  let i = 1;
  for (; i < m; ++i) {
    sum_1 = sum_1 + i;
  }

  let sum_2 = 0;
  let j = 1;
  for (; j < n; ++j) {
    sum_2 = sum_2 + j;
  }

  return sum_1 + sum_2;
}

Приведенный выше код также является суммированием, размер данных sum_1 равен m, а размер данных sum_2 равен n, поэтому временная сложность равна O(m+n).

Формула: T1(m) + T2(n) = O(f(m) + g(n)) .

    1. Умножение нескольких масштабов: например, метод имеет два параметра для управления количеством двух циклов, затем умножается их сложность.
function cal(m, n) {
  let sum_3 = 0;
   let i = 1;
   let j = 1;
   for (; i <= m; ++i) {
     j = 1; 
     for (; j <= n; ++j) {
       sum_3 = sum_3 +  i * j;
     }
   }
}

Приведенный выше код также представляет собой суммирование, два слоя цикла for, размер данных sum_3 равен m и n, поэтому временная сложность равна O(m*n).

Формула: T1(m) * T2(n) = O(f(m) * g(n)) .

3.4 Общий анализ временной сложности

    1. Полиномиальный порядок: по мере роста размера данных время выполнения и пространство, занимаемое алгоритмом, увеличиваются пропорционально полиномиальному.

Включая O(1) (постоянный порядок), O(logn) (логарифмический порядок), O(n) (линейный порядок), O(nlogn) (линейный логарифмический порядок), O(n2) (квадратный порядок), O(n3) (кубический порядок).

Кроме O(logn), O(nlogn), все остальное видно из приведенных выше примеров.

Следующие примеры иллюстрируютO (logn) (логарифмический порядок):

let i=1;
while (i <= n)  {
   i = i * 2;
}

Код начинается с 1 и каждый раз, когда цикл зацикливается, умножается на 2. Когда число больше n, цикл завершается.

На самом деле в средней школе были геометрические ряды, i — значение геометрического ряда. В математике есть такое:

20 21 22 ... 2k ... 2x = n

Итак, пока мы знаем, каково значение x, мы знаем, сколько раз выполняется эта строка кода, на 2x= n Найдите x, что в математике дает x = log2н . Таким образом, временная сложность приведенного выше кода равна O(log2н).

На самом деле, будь то основание 2, основание 3 или основание 10, мы можем записать всю логарифмическую временную сложность как O(logn). Зачем?

Поскольку логарифмы можно преобразовывать друг в друга, log3n = log32 * log2п, так о (журнал3n) = O(C * log2n), где C=log32 - постоянная.

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

следовательно,В методе представления логарифмической временной сложности мы игнорируем «основание» логарифма и выражаем его единообразно как O (logn).

Следующие примеры иллюстрируютO(nlogn) (логарифмический порядок):

function aFun(n){
  let i = 1;
  while (i <= n)  {
     i = i * 2;
  }
  return i
}

function cal(n) { 
   let sum = 0;
   for (let i = 1; i <= n; ++i) {
     sum = sum + aFun(n);
   }
   return sum;
 }

Временная сложность aFun равна O(logn), а временная сложность cal равна O(n), поэтому временная сложность приведенного выше кода равна T(n) = T1(logn) * T2(n) = O(logn * n) = O(nlogn).

    1. Неполиномиальный порядок: с ростом размера данных время выполнения и занимаемая память алгоритма резко возрастают, а производительность этого типа алгоритма крайне низкая.

в том числе О(2n) (экспоненциальный порядок), O(n!) (факториальный порядок).

O(2n) (экспоненциальный порядок) пример:

aFunc( n ) {
    if (n <= 1) {
        return 1;
    } else {
        return aFunc(n - 1) + aFunc(n - 2);
    }
}

Справочный ответ: Очевидно количество прогонов, T(0) = T(1) = 1, а T(n) = T(n - 1) + T(n - 2) + 1, где 1 - одно выполнение сложения в нем . Очевидно, что T(n) = T(n - 1) + T(n - 2) являетсяПоследовательность Фибоначчи, с помощью индукционного доказательства можно показать, что при n >= 1 T(n) n, а T(n) >= (3/2) при n > 4n. Таким образом, временная сложность этого метода может быть выражена как O((5/3)n), что упрощается до O(2n). Видно, что время работы, необходимое для этого метода, увеличивается в геометрической прогрессии. Если вам интересно, вы можете попробовать использовать размер ввода 1, 10, 100, чтобы проверить время работы алгоритма, я думаю, каждый почувствует бесконечное очарование временной сложности.

3.5 Классификация временной сложности

Временную сложность можно разделить на:

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

Например:

// n 表示数组 array 的长度
function find(array, n, x) {
  let i = 0;
  let pos = -1;
  for (; i < n; ++i) {
    if (array[i] == x) {
      pos = i; 
      break;
    }
  }
  return pos;
}

Функция, реализованная функцией find, заключается в том, чтобы найти элемент, значение которого равно x в массиве, и вернуть значение индекса или -1, если он не найден.

Временная сложность в лучшем случае, временная сложность в худшем случае

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

Итак, приведенный выше код最好情况时间复杂度равно О (1),最坏情况时间复杂度равно О (n).

Средняя временная сложность дела

Как проанализировать среднюю временную сложность? Разница в величине сложности кода в разных ситуациях представлена ​​средневзвешенным значением времени выполнения кода во всех возможных ситуациях.

Позиция искомой переменной x в массиве, n+1 случаев: в позиции 0～n-1 массива и не в массиве. Мы складываем количество элементов, которые необходимо пройти в каждом случае, а затем делим на n+1, чтобы получить среднее число элементов, которые необходимо пройти, а именно:

Коэффициенты, младшие порядки и константы опущены, поэтому после упрощения этой формулы полученное平均时间复杂度равно О (n).

Мы знаем, что искомая переменная x либо есть в массиве, либо нет в массиве. Вероятности для обоих случаев сложно подсчитать, и мы предполагаем, что вероятность оказаться в массиве и не оказаться в массиве равна 1/2. Кроме того, вероятность того, что данные будут найдены в n позициях от 0 до n-1, одинакова и равна 1/n. Следовательно, согласно правилу умножения вероятности, вероятность того, что данные будут найдены в любой позиции в 0～n-1, равна 1/(2n).

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

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

Таким образом, согласно сделанному выше выводу, мы получаем平均时间复杂度Все еще О (n).

Амортизированная временная сложность

Амортизированная временная сложность — это особый вид средней временной сложности (сценарий приложения очень особенный и очень ограниченный, поэтому я не буду говорить об этом здесь).

3.6 Резюме временной сложности

Время, затраченное на общую временную сложность, составляет:

O(1) < O(logn) < (n) < O(nlogn) < O(n2) < O(n3) < O(2n) < O(n!) < O(nn)

Общая временная сложность:

3.7 Анализ космической сложности

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

По аналогии полное название пространственной сложностиасимптотическая пространственная сложность(асимптотическая пространственная сложность), указывающаяЗависимость роста между объемом памяти алгоритма и размером данных.

Определение: Пространственная сложность алгоритма реализуется путем вычисления объема памяти, необходимого для алгоритма.Формула расчета пространственной сложности алгоритма записывается как:S(n) = O(f(n)), где n — размер задачи, а f(n) — функция памяти, занимаемой оператором относительно n.

function print(n) {
 const newArr = []; // 第 2 行
 newArr.length = n; // 第 3 行
  for (let i = 0; i <n; ++i) {
    newArr[i] = i * i;
  }

  for (let j = n-1; j >= 0; --j) {
    console.log(newArr[i])
  }
}

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

Наша общая сложность пространства является O (1), O (n), O (n2), Как o (logn), o (nlogn), такой как порядок сложности, меньше, чем обычно.

4. Как освоить метод анализа сложности?

Ключ к анализу сложности лежит в практике, так называемая практика делает совершенным.

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

5. Наконец

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

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

Справочная статья:

1. Анализ сложности (часть 1): как анализировать и подсчитывать эффективность выполнения и потребление ресурсов алгоритмов?

2. (Структура данных) 10 минут, чтобы получить временную сложность алгоритма.

笔芯

Категории