В новом году поделюсь с вами простым и важным пунктом знаний:временная сложность и пространственная сложность. Потому что в предыдущих статьях упоминалась временная сложность, и некоторым друзьям может быть непонятно. (ps: я надеюсь, что маленький друг, который оставил сообщение в моей прошлой статье, не будет разочарован, не торопитесь.)
Позвольте мне сначала задать вам вопрос для размышления, заголовок: сумма = 1+2+3+...+n, вычислите значение суммы.
Зачем нужен анализ сложности
- Изучение структур данных и алгоритмов связано с пониманием вопросов «быстроты» и «экономии», то есть того, как спроектировать код так, чтобы он работал быстрее и занимал меньше места. Так как же рассчитать эффективность выполнения кода? Здесь вступает в действие анализ сложности.
- Хотя мы можем точно рассчитать время выполнения кода, это также имеет много ограничений.
- Разница в масштабе данных напрямую повлияет на результаты теста. Например, для одного и того же алгоритма сортировки, если порядок сортировки разный, итоговая эффективность вычислений будет разной, а если массив уже отсортирован, то время выполнения будет меньше. Например, если размер данных относительно невелик, результаты тестирования могут не отражать производительность алгоритма.
- Тестовая среда также повлияет на результаты теста. Например, если тестировать один и тот же набор кода на процессорах i3 и i7, то время тестирования на i7 точно будет меньше, чем на i3.
Следовательно, необходим метод, который может грубо оценить время выполнения кода без измерения точных результатов тестирования. ЭтоАнализ сложности.
Обозначение сложности Big O
Чтобы начать с примера, пожалуйста, оцените время выполнения кода ниже
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
sum += i; // 4
} //5
} //6
Мы предполагаем, что время выполнения каждой строки кода одинаково, обозначается как t, тогда вторая строка в приведенной выше функции занимает 1 t времени, третья строка и четвертая строка требуют n t времени соответственно, тогда этот код Общее выполнение время равно (2n+1)*t.
Затем в соответствии с приведенным выше методом анализа оцените время выполнения следующего кода.
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
for (var j = 0; j < n; j++) { // 4
sum = sum + i + j; // 5
}
}
}
Строка 2 занимает один t раз, строка 3 занимает n t времени, а каждая строка 4 и 5 занимает n2время, то общее время выполнения этого кода равно (2n2+n+1)*t раз.
С математической точки зрения можно вывести правило: общее время выполнения T(n) кода пропорционально количеству исполнений каждой строки кода.
T(n) = O(f(n))
В этой формуле T(n) представляет собой время выполнения кода; n представляет собой размер данных; f(n) представляет собой сумму количества выполнений каждой строки кода; O представляет время выполнения кода. code T(n) и f(n) Выражение пропорционально.
Таким образом, время выполнения двух вышеуказанных функций можно обозначить как T(n) = O(2n+1) и T(n) = O(2n2+n+1). ЭтоОбозначение временной сложности Big O, который не представляет реальное время выполнения кода, а скорееТенденция изменения кода с ростом размера данных, именуемыйвременная сложность.
А когда n велико, мы можем игнорировать постоянный член и оставить только один максимальный порядок. Таким образом, приведенное выше время выполнения кода можно просто обозначить как T(n) = O(n) и T(n) = O(n).2).
анализ временной сложности
Итак, как проанализировать временную сложность куска кода, вы можете использовать следующие методы
1. Сосредоточьтесь только на той части кода, которая выполняет больше всего циклов
Когда мы анализируем временную сложность фрагмента кода, нам нужно сосредоточиться только на фрагменте кода с наибольшим количеством циклов. Например, в первом фрагменте кода
function total(n) { // 1
var sum = 0; // 2
for (var i = 0; i < n; i++) { // 3
sum += i; // 4
} //5
} //6
Только 3-я и 4-я строки выполняются больше всего раз, а они выполняются n раз соответственно, тогда постоянный член игнорируется, поэтому временная сложность этого кода равна O(n).
2. Закон сложения: общая сложность равна сложности кода с наибольшей величиной.
Например, посмотрите на временную сложность следующего кода.
function total(n) {
// 第一个 for 循环
var sum1 = 0;
for (var i = 0; i < n; i++) {
for (var j = 0; j < n; j++) {
sum1 = sum1 + i + j;
}
}
// 第二个 for 循环
var sum2 = 0;
for(var i=0;i<1000;i++) {
sum2 = sum2 + i;
}
// 第三个 for 循环
var sum3 = 0;
for (var i = 0; i < n; i++) {
sum3 = sum3 + i;
}
}
Мы сначала анализируем временную сложность каждого цикла for отдельно, а затем принимаем наибольшую из них за временную сложность всего кода.
Временная сложность первого цикла for равна O(n2).
Второй цикл for выполняется 1000 раз, что является постоянным порядком величины.Хотя это повлияет на время выполнения кода, когда n бесконечно, его можно игнорировать. Временная сложность этого кода незначительна, поскольку сам по себе он не влияет на тенденцию роста.
Временная сложность третьего цикла for равна O(n).
В общем случае берите наибольший порядок, поэтому временная сложность всего кода равна O(n2).
3. Закон умножения: Сложность вложенного кода равна произведению сложности кода внутри и вне гнезда.
Например, посмотрите на временную сложность следующего кода.
function f(i) {
var sum = 0;
for (var j = 0; j < i; j++) {
sum += j;
}
return sum;
}
function total(n) {
var res = 0;
for (var i = 0; i < n; i++) {
res = res + f(i); // 调用 f 函数
}
}
Глядя только на временную сложность общей функции, мы получаем T1(n)=O(n), но учитывая, что временная сложность функции f также равна T2(n)=O(n). Таким образом, временная сложность всего кода равна T(n) = T1(n) * T2(n) = O(n*n)=O(n2).
Несколько общих анализ временной сложности
Глядя только на самый высокий уровень сложности, эффективность на рисунке ниже снижается.
1. O(1)
O(1) — это просто представление временной сложности с постоянным уровнем, а не просто одна строка кода, например следующий код
function total() {
var sum = 0;
for(var i=0;i<100;i++) {
sum += i;
}
}
Хотя строк так много, даже если цикл for выполняется 100 раз, время выполнения кода не увеличивается с увеличением n, поэтому сложность такого кода составляет O(1).
2. О(логн), О(nлогн)
Общий код для логарифмической временной сложности выглядит следующим образом.
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i;
i = i * 2;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 2) {
sum += i;
}
}
У этих двух функций есть одна общая черта: переменная i начинается с 1 и при каждом повторении цикла умножается на 2. Когда она больше n, цикл завершается. На самом деле значение i представляет собой пропорциональную последовательность, подобную следующей
20 21 22 ... 2k... 2x =n;
Итак, пока вы знаете значение x, вы можете знать количество выполнений этих двух функций. Наю 2x= n дает x = log2n, поэтому временная сложность этих двух функций равна O(log2н).
Давайте посмотрим на временную сложность следующих двух функций.
function total1(n) {
var sum = 0;
var i = 1;
while (i <= n) {
sum += i;
i = i * 3;
}
}
function total2(n) {
var sum = 0;
for (var i = 1; i <= n; i = i * 3) {
sum += i;
}
}
Из приведенного выше видно, что временная сложность этих двух функций равна O(log3н) .
Поскольку мы можем игнорировать константы и основания в логарифмах, в логарифмической сложности она выражается как O(logn); тогда смысл O(nlogn) очень ясен, а временная сложность O(logn) выполняется n раз.
3. О(м+п), О(м*п)
Давайте посмотрим на особую временную сложность кода, например
function total(m,n) {
var sum1 = 0;
for (var i = 0; i < n; i++) {
sum1 += i;
}
var sum2 = 0;
for (var i = 0; i < m; i++) {
sum2 += i;
}
return sum1 + sum2;
}
Поскольку мы не можем оценить, какая величина m и n больше, мы не можем игнорировать одну из них.Сложность этой функции определяется величиной двух данных, поэтому временная сложность этой функции составляет O (m + n) ; тогда временная сложность O(m*n) аналогична.
анализ пространственной сложности
Пространственная сложность может быть рассчитана аналогично временной сложности. Так называемая пространственная сложностьПредставляет взаимосвязь между объемом памяти алгоритма и размером данных..
Например, проанализируйте объемную сложность следующего кода:
function initArr(n) {
var arr = [];
for (var i = 0; i < n; i++) {
arr[i] = i;
}
}
В соответствии с расчетом временной сложности, игнорируя постоянный порядок величины, для каждого назначения массива будет применяться переменная хранения пространства, поэтому сложность пространства для этой функции составляет O (n).
Общая сложность пространства составляет только O (1), O (n), O (n2). Другие слова используются редко.
мысль вопрос ответ
Теперь давайте вернемся к задуманному в начале вопросу, реализация кода очень проста:
function total(n) {
var sum = 0;
for (var i = 1; i <= n; i++) {
sum += i;
}
return sum;
}
Временная сложность этой функции уже должна быть легко видна, она составляет O(n).
Я думаю, что эта временная сложность немного высока, я хочу, чтобы функция временной сложности O (1) реализовывала этот алгоритм, возможно ли это?
Да, маленький математический волшебник Гаусс научил нас следующему трюку.
function total(n) {
var sum = n*(n+1)/2
return sum;
}
Временная сложность этой функции составляет всего O (1).Когда размер данных относительно велик, следующая функция значительно более эффективна, чем приведенная выше функция?
Суммировать
сложностьТакже известен какАсимптотическая сложность,включаютвременная сложностьикосмическая сложность, один представляет скорость выполнения, а другой представляет потребление памяти. Он используется для анализа зависимости роста между эффективностью выполнения алгоритма и размером данных. Его можно представить примерно. Чем выше сложность алгоритма, тем ниже эффективность выполнения.
Изучив анализ сложности, сможете ли вы избежать написания неэффективного кода? Давайте проанализируем ваш код.
фокус
Если есть какие-либо ошибки или опечатки, пожалуйста, оставьте мне сообщение, чтобы указать, спасибо.
Увидимся в следующий раз.