Подпишитесь на официальный аккаунт MageByte и поставьте звездочку, чтобы получать последние галантереи. Фон официальной учетной записи ответил «Jiaqun», чтобы войти в группу технического обмена, чтобы получить больше технического роста.
Ранее мы говорили о важности алгоритмовСтруктуры данных и алгоритмы Начало, сегодня мы начинаем учиться анализировать и считать эффективность выполнения и потребление ресурсов алгоритма? Пожалуйста, прочитайте эту статью одну за другой.
Структуры данных и алгоритмы по своей сути решают проблемы «быстро» и «экономно», то есть как заставить код работать быстрее и экономить место для хранения. Постройте Ferrari, которая не только быстро едет, но и экономит топливо, имеет хорошие алгоритмы и структуры данных, программа работает быстро, экономит память и работает долго без сбоев, как спортивный автомобиль, который долго работает без каких-либо отклонений от нормы». Автомобильный шок», но и быстро. Поэтому быстро садитесь в машину, вместе изучайте структуру данных и алгоритм и садитесь в машину «постоянно», чтобы научиться определять, быстрая ли спортивная машина или нет, и является ли она экономичной или нет.
Здесь мы будем использовать то, о чем мы сегодня поговорим: анализ временной и пространственной сложности. Пока мы говорим о структурах данных и алгоритмах, мы должны анализировать сложность времени и пространства.Анализ сложности является сутью всего обучения алгоритму.Пока вы его освоите, вы в основном освоите половину содержания структур данных и алгоритмов.. Это точно так же, как метод внутренней силы ума, высшие боевые искусства также должны сочетаться с методом удивительного ума.
Только изучив стандарты тестирования, мы можем написать и построить наш код «Феррари» в соответствии со стандартами при проектировании.
Зачем нужен анализ сложности
Могут быть некоторые сомнения, я снова запускаю код, и через статистику и мониторинг я могу получить время выполнения и объем памяти алгоритма. Почему необходимо проводить анализ временной и пространственной сложности? Может ли этот метод анализа быть более точным, чем данные, которые я получаю, фактически запуская его?
Такого рода вещи должны быть испытаны сами по себе, без разумного метода, чтобы предсказать, что мы хотим знать заранее, как гадалка. Многие книги по структурам данных и алгоритмам также дают этому методу имя, называемоеапостериорная статистика. Однако этот статистический метод имеет очень большие ограничения.
1. Результаты тестирования сильно зависят от тестовой среды
Различия в оборудовании в тестовой среде могут сильно повлиять на результаты тестирования. Например, давайте возьмем один и тот же фрагмент кода и запустим его на процессоре Intel Core i7 и процессоре Intel Core i3.Излишне говорить, что процессор i7 работает намного быстрее, чем процессор i3.
Это как управлять одной и той же машиной на авеню Бэйхуань в Шэньчжэне и в маленькой долине в моей сельской местности.
2. На результаты тестирования сильно влияет размер данных
Мы поговорим об алгоритмах сортировки позже, но давайте возьмем это в качестве примера. Для одного и того же алгоритма сортировки порядок сортируемых данных разный, и время выполнения сортировки будет сильно различаться.
В крайних случаях, если данные уже отсортированы, алгоритму сортировки ничего делать не нужно, а время выполнения очень короткое. Кроме того, если размер тестовых данных слишком мал, результаты тестов могут не отражать в действительности производительность алгоритма.
Например, для мелкомасштабной сортировки данных сортировка вставками может оказаться быстрее, чем быстрая сортировка!
так,Нам нужен метод, который может грубо оценить эффективность выполнения алгоритма без конкретных тестовых данных для тестирования.. Это метод анализа временной и пространственной сложности, о котором мы поговорим сегодня.
Обозначение сложности Big O
Эффективность выполнения алгоритма, грубо говоря, — это время выполнения кода алгоритма. Но как получить время выполнения куска кода «невооруженным глазом», не запуская код? Это как проверять мощность и расход топлива автомобиля.
Найдите кумулятивную сумму 1,2,3…n. Теперь давайте вместе оценим время выполнения этого кода.
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
С точки зрения процессора каждая строка этого кода делает что-то вроде:читать данные-операция-записать данные. Хотя количество выполнений ЦП и время выполнения, соответствующее каждой строке кода, различаются, здесь мы делаем только приблизительную оценку, поэтому можно предположить, что время выполнения каждой строки кода одинаково.unit_timeЕдиница времени.
Исходя из этого предположения, каково общее время выполнения этого кода?
Строки 2 и 3 требуют по 1 каждойunit_timeВремя выполнения , строки 4 и 5 выполняются n раз, поэтому необходимо2n*unit_time, поэтому общее время выполнения этого кода равно(2n+2)*unit_time. Видно, что,Время выполнения T(n) всего кода пропорционально количеству выполнений каждой строки кода..
Продолжим анализ следующего кода
int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
Мы по-прежнему предполагаем, что время выполнения каждого оператора равноunit_time. Каково общее время выполнения T(n) этого кода?
Строки 2, 3, 4, каждая требует 1unit_timeВремя выполнения 5-й и 6-й строк кода выполняется n раз, что требует2n * unit_timeВремя выполнения 7-й и 8-й строк кода выполняется n^2^ раз, поэтому требуется время выполнения 2n^2^ * unit_time. Следовательно, общее время выполнения всего кода равно T(n) = (2n^2^+ 2n + 3)*unit_time.
Хотя мы не знаем конкретное значение unit_time, в процессе вывода времени выполнения этих двух фрагментов кода мы можем получить очень важное правило, то есть ==Время выполнения T(n) всего кода пропорционально количеству выполнений n каждой строки кода.==.
Мы можем обобщить этот закон в виде формулы. Осторожно, приближается Большое О!
Среди них «T(n)», о котором мы уже говорили, представляет собой время выполнения кода, n представляет размер размера данных, «f(n)» представляет собой сумму количества повторений каждой строки кода. код выполняется. Поскольку это формула, используйтеПредставлять. Буква O в формуле означает, что время выполнения T(n) кода пропорционально выражению f(n).
Так, в первом примере, T(n) = O(2n^2^+2n+3) во втором примере. ЭтоОбозначение временной сложности Big O.
Временная сложность Big O на самом деле не выражает реальное время выполнения кода, а выражаетТенденция времени выполнения кода с увеличением размера данных, поэтому его еще называютАсимптотическая временная сложность(асимптотическая временная сложность), сокращенновременная сложность. Выбитое на доске, оно выражает тенденцию изменений, а не реальное время выполнения.
Когда n велико, вы можете представить его как 100000, 1000000. Три части == низкого порядка, константы и коэффициента == в формуле не контролируют тенденцию роста, поэтому их можно игнорировать.Нам просто нужно записать максимальную величину, если временная сложность двух только что упомянутых фрагментов кода выражена в большой нотации O, ее можно записать как: ?T(n) = O(n)?; ?T(n) = O(n^2) .
анализ временной сложности
Происхождение и метод представления большой временной сложности O были введены ранее. Теперь давайте посмотрим, как проанализировать временную сложность куска кода? Есть еще три практических метода, которыми можно поделиться.
1. Сосредоточьтесь только на той части кода, которая выполняет больше всего циклов
Метод представления сложности Big O представляет собой только меняющуюся тенденцию. Обычно мы игнорируем константы, младшие порядки и коэффициенты в формуле и должны записывать только величину наибольшего порядка. так,Когда мы анализируем временную сложность алгоритма или фрагмента кода, мы фокусируемся только на фрагменте кода, который выполняет наибольшее количество циклов.. Сначала поймай вора и первым поймай короля.
Порядок величины n времени выполнения этого базового кода равен временной сложности всего анализируемого кода.
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
Вторая и третья строки кода представляют собой время выполнения постоянного уровня, не зависящее от размера n, поэтому это не влияет на сложность.
4-я и 5-я строки кода имеют наибольшее время выполнения цикла, поэтому этот код следует проанализировать. Как мы упоминали ранее, эти две строки кода выполняются n раз, поэтому общая временная сложность составляет O(n).
2. Закон сложения: общая сложность равна сложности кода с наибольшей величиной.
Глядя на следующий код, вы можете попытаться сначала проанализировать его, а затем посмотреть вниз, чтобы увидеть, совпадает ли моя идея анализа.
int cal(int n) {
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
int sum_3 = 0;
int i = 1;
int 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;
}
Этот код разделен на три части, которые должны найти сумму_1, сумму_2 и сумму_3. Мы можем проанализировать временную сложность каждой части отдельно, сложить их вместе и взять за сложность всего кода тот, у которого порядок больше.
- Какова временная сложность первого сегмента? Этот код зацикливается 100 раз, поэтому его выполнение занимает постоянное время, независимо от размера n.
- Здесь я хочу еще раз подчеркнуть, даже если этот код повторяется 10 000 раз, 100 000 раз, пока это известное число, оно не имеет ничего общего с n, это все равно время выполнения на постоянном уровне. Когда n бесконечно, им можно пренебречь. Хотя это сильно повлияет на время выполнения кода, но вернемся к концепции временной сложности,Он представляет собой тенденцию изменения эффективности выполнения алгоритма и роста масштаба данных, поэтому независимо от того, насколько велико время выполнения константы, мы можем его игнорировать.. Потому что сам по себе он не влияет на тенденцию роста.
- Какова временная сложность второго кода и третьего кода? Ответ — O(n) и O(n^2^), вы легко сможете его проанализировать, поэтому я не буду повторяться.
Объединяя временную сложность этих трех частей кода, мы берем наибольший порядок величины. Следовательно, временная сложность всего кода равна O(n^2^). То есть:Общая временная сложность равна временной сложности кода с наибольшей величиной. Затем мы абстрагируем этот закон в формулу:
如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
3. Закон умножения: сложность вложенного кода равна произведению сложности кода внутри и вне гнезда
Я только что упомянул принцип сложения, принцип умножения, упомянутый здесь, и так далее, вы также должны быть в состоянии «угадать» формулу. это наименее эффективное
Если T1(n)=O(f(n)), T2(n)=O(g(n)), то T(n)=T1(n)*T2(n)=O(f(n)) * О (г (п)) = О (ф (п) * г (п)).
То есть, если предположить, что T1(n) = O(n) и T2(n) = O(n2), то?T1(n) * T2(n) = O(n^3)?. Реализуя конкретный код, мы можем думать о правиле умножения каквложенный цикл
int cal(int n) {
int ret = 0;
int i = 1;
for(x=1; i <= n; x++){
for(i = 1; i <= n; i++) {
j = i;
j++;
}
}
}
Давайте рассмотрим только функцию cal(). Предполагая, что строки 5-8 являются обычной операцией, временная сложность строки 4 равна T1(n) = O(n). Но сама функция 5-8 не является простой операцией, ее временная сложность равна T2(n) = O(n), поэтому временная сложность всей функции cal() равна ?T(n) = T1(n) * T2(n) = O(n*n) = O(n^2)?.
Несколько распространенных примеров временной сложности
Хотя код сильно различается, не так много общих показателей уровня сложности. Мой брат немного подытожил, эти шкалы сложности почти перекрывают шкалы сложности всего кода, который можно будет трогать в будущем.
Сосредоточьтесь на учениках.
- постоянный порядок
- логарифмический
- Линейный порядок
- Линейный логарифмический порядок
- Квадратный порядок O(n^2^), кубический порядок O(n^3^)….k порядок O(n^k^)
- Экспоненциальный порядок O (2 ^ n ^)
- Факторный порядок O (n!)
Только что перечисленные меры сложности можно условно разделить на две категории:Полиномиальная величинаа такженеполиномиальная величина. Среди них всего две неполиномиальные величины: ?O(2^n)? и O(n!).
По мере того, как размер данных n становится все больше и больше, время выполнения неполиномиальных алгоритмов резко возрастает, а время выполнения для решения задачи увеличивается бесконечно. Следовательно, алгоритмы с неполиномиальной временной сложностью на самом деле являются очень неэффективными алгоритмами. Поэтому я не буду говорить о временной сложности NP.
В основном мы рассматриваем некоторые общиеПолиномиальная временная сложность.
1. O(1) Убить одним ударом
Прежде всего, мы должны прояснить концепцию: O(1) — это просто представление временной сложности постоянного уровня и не означает, что выполняется только одна строка кода. Например, этот код, даже с тремя строками, имеет временную сложность O(1) вместо O(3).
int a = 1;
int b = 2;
int c = 3;
нашHashMap get()、put()На самом деле, это O(1) временная сложность.
Пока время выполнения кода не увеличивается с увеличением n, временная сложность кода равна O(1). Или,В общем, пока в алгоритме нет операторов цикла или рекурсивных операторов, даже если есть тысячи строк кода, временная сложность равна 0 (1)..
2. О(логн), О(nлогн)
Логарифмическая временная сложность очень распространена, и ее также труднее всего анализировать.
i=1;
while (i <= n) {
i = i * 2;
}
Согласно методу анализа сложности, о котором мы говорили ранее, третья строка кода является наиболее исполняемым циклом. Следовательно, пока мы можем подсчитать, сколько раз выполняется эта строка кода, мы можем знать временную сложность всего кода.
** Как видно из кода, значение переменной i начинается с 1 и умножается на 2 каждый раз, когда цикл зацикливается. Когда оно больше n, цикл завершается. **Помните серию пропорциональных чисел, которая была у нас в старшей школе? На самом деле значение переменной i представляет собой пропорциональную последовательность. Если я перечислю их один за другим, это должно выглядеть так:
?2^0 2^1 2^2 ……..2^x = n?
Итак, пока мы знаем, каково значение x, мы знаем, сколько раз выполняется эта строка кода.Решение задачи x с помощью 2^x^=n Мы думаем, что должны были выучить это в старшей школе, поэтому я не буду говорить больше. х=журнал2n, поэтому временная сложность этого кода равна O(log2н).
Я немного изменил код, какова временная сложность этого кода?
i=1;
while (i <= n) {
i = i * 3;
}
Легко видеть, что временная сложность этого кода равна O(log3н).
На самом деле, будь то основание 2, основание 3 или основание 10, мы можем записать временную сложность всех логарифмов как O(logn). Зачем?
Мы знаем, что логарифмы можно преобразовывать друг в друга, log3n равно log32 * log2n, так что O(log3n) = O(C * log2n), где C=log32 - постоянная. На основе одной из наших предыдущих теорий:При использовании Big O для обозначения сложности коэффициенты можно игнорировать, т. Е. O (Cf (n)) = O (f (n)). Итак, О(лог.2n) равно O(log3н). Поэтому при представлении логарифмической временной сложности мы игнорируем «основание» логарифма и выражаем его единообразно как O(logn).
Если вы понимаете O(logn), о котором я упоминал ранее, то O(nlogn) легко понять. Помните правило умножения, о котором мы только что говорили? Если временная сложность фрагмента кода равна O(logn), и мы выполняем цикл n раз, временная сложность равна O(nlogn). Кроме того, O(nlogn) — очень распространенная временная сложность алгоритма. Например, временная сложность сортировки слиянием и быстрой сортировки составляет O(nlogn).
следующим образом, внутренний цикл while заменяется внешним циклом for за O(logn). Так что это O (nlogn)
for(m = 1; m < n; m++) {
i = 1;
while(i < n) {
i = i * 2;
}
}
3. О(м+п), О(м*п)
Поговорим об отличной от предыдущей временной сложности, сложности кодапо шкале двух данныхпринимать решение.
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
Как видно из кода, m и n представляют два размера данных. Мы не можем заранее оценить, какая величина m и n больше, поэтому, когда мы выражаем сложность, мы не можем просто использовать правило сложения и опустить одно из них. Таким образом, временная сложность приведенного выше кода составляет O(m+n).
Ввиду этой ситуации исходное правило сложения некорректно, нужно изменить правило сложения на: T1(m) + T2(n) = O(f(m) + g(n)). Но правило умножения сохраняется: T1(m)*T2(n) = O(f(m) * f(n)).
**4.Линейный порядок O(n)**
Сколько раз выполняется этот код?
for(i=1; i<=n; i++) {
j = i;
j++;
}
Строка 1 будет выполнена n раз, строки 2 и 3 будут выполнены n раз соответственно, общее время выполнения равно 3n + 1 раз, тогда ее представление временной сложности будет O(3n + 1) ? Нет !
Опять таки:«Обозначение Big O не используется для реального представления времени выполнения алгоритма, оно используется для представления возрастающей тенденции времени выполнения кода»..
Таким образом, его временная сложность на самом деле O (n);
Квадратный порядок O (n²)
for(x=1; i <= n; x++){
for(i = 1; i <= n; i++) {
j = i;
j++;
}
}
Снова вложите код O(n), и его временная сложность составит O(n²).
Кубический порядок O (n³), порядок степени K O (n ^ k ^)
Просто обратитесь к приведенному выше O (n²), чтобы понять, что O (n³) эквивалентно трем слоям из n циклов, а другие аналогичны.
Анализ сложности воздуха
После понимания содержания, упомянутого выше, метод анализа пространственной сложности очень прост в освоении.
Полное название временной сложностиАсимптотическая временная сложность,Представляет растущую взаимосвязь между временем выполнения алгоритма и размером данных.. По аналогии полное название пространственной сложностиасимптотическая пространственная сложность,Представляет зависимость роста между объемом памяти алгоритма и размером данных..
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
}
Как и при анализе временной сложности, мы видим, что во второй строке кода мы применяем переменную i для хранения пространства, но она имеет постоянный порядок и не имеет ничего общего с размером данных n, поэтому мы можем ее игнорировать. Строка 3 применяется для массива типа int размера n. Кроме того, остальная часть кода не занимает больше места, поэтому объемная сложность всего кода составляет O (n).
Если провести неуместную аналогию, то наши мобильные телефоны становятся все лучше и лучше, а мобильные телефоны становятся все тоньше и тоньше. Занимаемый объем становится все меньше и меньше. То есть для размещения деталей используется лучшая конструкция пресс-формы, и пресс-форма похожа на объем с меньшей пространственной сложностью, который вмещает больше оригиналов.
Наша общая пространственная сложность равна O(1), O(n), O(n2), а логарифмическая сложность, такая как O(logn) и O(nlogn), обычно не используется. Более того, анализ пространственной сложности намного проще, чем анализ временной сложности. Итак, для космической сложности достаточно освоения того, что я только что сказал.
Пространственная сложность O(1)
Если временное пространство, необходимое для выполнения алгоритма, не меняется с размером переменной n, то есть пространственная сложность алгоритма является константой, которая может быть выражена как O (1).
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
Пространство, выделяемое i, j и m в коде, не меняется с объемом обрабатываемых данных, поэтому его пространственная сложность S(n) = O(1).
Пространственная сложность O (n)
int[] m = new int[n]
for(i=1; i <= n; ++i) {
j = i;
j++;
}
В этом коде в первой строке создается новый массив. Размер этих данных равен n. Хотя позже есть цикл, но новое пространство не выделяется, поэтому объемная сложность этого кода в основном зависит от первой строки. Да, то есть S(n) = O(n).
Суммировать
На этом знания базового анализа сложности заканчиваются, подведем итоги.
Сложность также называется асимптотической сложностью, включая временную сложность и пространственную сложность.Он используется для анализа зависимости роста между эффективностью выполнения алгоритма и размером данных.Его можно грубо выразить.Чем выше сложность алгоритма, тем ниже эффективность выполнения.
Не так много общих сложностей, от низкого до высокого порядка: O (1), O (logn), O (n), O (nlogn), O (n ^ 2 ^). Изучив всю колонку, вы обнаружите, что почти все структуры данных и алгоритмы достаточно сложны, чтобы использовать их.
Кто-то говорит, что мы проведем тестирование производительности перед проектом, а потом проанализируем временную и объемную сложность кода, разве это лишнее? Кроме того, является ли пустой тратой времени анализ временной и пространственной сложности каждого фрагмента кода? Что вы думаете об этом вопросе?
Добро пожаловать в группу, чтобы поделиться с нами, мы дадим отзыв как можно скорее. Подпишитесь на официальный аккаунт MageByte и отвечайте в группе в фоновом режиме. В группе есть большие ребята, работающие в первоклассных интернет-компаниях, которые учатся друг у друга и идут к вершине.
использованная литература
- «Красота структур данных и алгоритмов»