Я старший инженер. Недавно я подумывал о том, чтобы почистить алгоритмы, чтобы сделать их более продвинутыми. Однако, когда я собирался вспомнить структуру данных, которую я изучил в колледже и на собеседованиях, я обнаружил, что моя память о сложности этот алгоритм был всего ОООООООО
Статья включена в GitHubJavaKeeper, N-линия Интернет-разработка основных навыков спектра оружия
Алгоритм — это набор методов, используемых для обработки данных и решения программных проблем. Для одной и той же задачи, используя разные алгоритмы, конечный результат может быть одинаковым, но ресурсы и время, затраченные на процесс, будут сильно различаться.
Так как же нам измерить плюсы и минусы разных алгоритмов?
В основном он рассматривается из двух измерений «времени» и «пространства», занимаемых алгоритмом.
- Измерение времени: относится ко времени, которое требуется для выполнения текущего алгоритма, которое мы обычно описываем как «временную сложность».
- Размер пространства: относится к тому, сколько памяти требуется для выполнения текущего алгоритма, который мы обычно описываем как «пространственная сложность».
Поэтому оценка эффективности алгоритма в основном зависит от его временной и пространственной сложности. Однако иногда время и пространство являются «рыбой и медвежьей лапой» и не могут иметь и того, и другого, поэтому нам нужно найти баланс.
временная сложность
Время, необходимое для выполнения алгоритма, не может быть рассчитано теоретически, и его необходимо запустить на компьютере, чтобы узнать его. Но нам невозможно и не нужно тестировать каждый алгоритм на компьютере, нам просто нужно знать, какой алгоритм требует больше времени, а какой меньше времени. И время, затрачиваемое алгоритмом, пропорционально количеству выполнений операторов в алгоритме, какой бы алгоритм ни выполнял больше операторов, он занимает больше времени. Количество раз, которое оператор выполняется в алгоритме, называется частотой оператора или "временная частота". Обозначается как T(n).
Во временной частоте T(n) n называется масштабом задачи, и когда n продолжает изменяться, временная частота T(n) также продолжает изменяться. Но иногда мы хотим знать, по какому закону она меняется при изменении, поэтому мы вводим понятие временной сложности. Временная сложность алгоритма также является измерением времени алгоритма, обозначаемым как: T(n) = O(f(n)). Это означает, что с увеличением размера задачи n скорость роста времени выполнения алгоритма такая же, как и скорость роста f(n), которая называется асимптотической временной сложностью алгоритма, обозначаемой каквременная сложность".
Мы называем это представление «Обозначение большого O",Также известен какпрогрессивная запись, представляет собой математическую запись, используемую для описания асимптотического поведения функции
Общие показатели временной сложности:
- постоянный порядок
- Линейный порядок
- Квадратный порядок
- кубический порядок
- логарифмический
- Линейный логарифмический порядок
- Порядок индекса
постоянный порядок
, что указывает на то, что время выполнения (или пространство, занимаемое во время выполнения) алгоритма всегда является константой, независимо от того, является ли набор входных данных большим или маленьким, до тех пор, пока нет сложных структур, таких как циклы, временная сложность алгоритма этот код O (1), например:
int i = 1;
int j = 2;
int k = i + j;
При выполнении вышеуказанного кода его потребление не увеличивается с ростом определенной переменной, поэтому какой бы длины ни был этот тип кода, даже если в нем десятки тысяч или сотни тысяч строк, его можно использовать
для представления его временной сложности.
Линейный порядок
, что указывает на то, что производительность алгоритма будет линейно меняться в зависимости от размера входных данных, таких как
for (int i = 0; i < n; i++) {
j = i;
j++;
}
В этом коде код в цикле for будет выполняться n раз, поэтому время, которое он потребляет, изменяется с изменением n, поэтому такой код можно использовать.
для представления его временной сложности.
Квадратный порядок
Указывает, что производительность алгоритма будет увеличиваться квадратично по мере роста входных данных. Наиболее распространенным является вложенный цикл по входным данным. Если уровень вложенности продолжит углубляться, производительность алгоритма станет кубической.
,
,
и так далее
for(x=1; i<=n; x++){
for(i=1; i<=n; i++){
j = i;
j++;
}
}
Экспоненциальный порядок
, что указывает на то, что производительность алгоритма будет увеличиваться в два раза с каждым увеличением входных данных.Типичным методом является реализация рекурсивного вычисления последовательности Фибоначчи.
int Fibonacci(int number)
{
if (number <= 1) return number;
return Fibonacci(number - 2) + Fibonacci(number - 1);
}
логарифмический
int i = 1;
while(i<n)
{
i = i * 2;
}
В приведенном выше коде в цикле while i каждый раз умножается на 2. После умножения i все ближе и ближе к n, пока i не станет меньше n и не выйдет. Попробуем решить ее, считая, что количество петель равно x, то есть 2 в степени x равно n, тогда x=log₂n получается из 2^x=n. Таким образом, временная сложность этого кода равна
Линейный логарифмический порядок
Линейный логарифмический порядок
, то есть временная сложность логарифмическая
Если код зацикливается n раз, то его временная сложность равна n * O(logN), т. е.
,следующее,
for(m=1; m<n; m++)
{
i = 1;
while(i<n)
{
i = i * 2;
}
}
Кроме того, на самом деле есть средняя сложность случая, лучшая временная сложность и худшая временная сложность. . . Как правило, если не указано иное, это наихудшая временная сложность значения.
космическая сложность
Пространственная сложность (Space Complexity) – это мера размера памяти, временно занимаемой алгоритмом во время выполнения процесса, которая также отражает тенденцию. Объем памяти, требуемый алгоритмом, представлен f(n). S(n)=O(f(n)), где n — размер задачи, а S(n) — сложность пространства.
Объем памяти, занимаемый алгоритмом в памяти компьютера, включает в себя три аспекта: объем памяти, занимаемый самим алгоритмом хранения, объем памяти, занимаемый входными и выходными данными алгоритма, и объем памяти, временно занимаемый алгоритмом во время его работы. операция.
В общем, когда программа выполняется на машине, помимо инструкций, констант, переменных и входных данных самой программы, ей также необходимо хранить блок памяти для операций с данными. Если пространство, занимаемое входными данными, зависит только от самой задачи и не имеет никакого отношения к алгоритму, необходимо проанализировать только вспомогательные блоки, необходимые для реализации алгоритма. Если вспомогательное пространство, необходимое для выполнения алгоритма, является постоянным по отношению к количеству входных данных, говорят, что алгоритм работает на месте, а объем памяти равен O (1). Когда пространственная сложность алгоритма линейно пропорциональна n, ее можно выразить как
, по аналогии с временной сложностью.
Наиболее часто используемые космические сложности: O (1), O (n), O (n²)
космическая сложность
Если временное пространство, необходимое для выполнения алгоритма, не меняется с размером переменной n, то есть пространственная сложность алгоритма является константой, которая может быть выражена как O (1) Пример:
int i = 1;
int j = 2;
++i;
j++;
int m = i + j;
Пространство, выделяемое i, j, m в коде, не меняется с количеством обрабатываемых данных, поэтому его пространственная сложность S(n) = O(1)
космическая сложность
int[] m = new int[n]
for(i=1; i<=n; ++i)
{
j = i;
j++;
}
В этом коде в первой строке создается новый массив. Размер этих данных равен n. Хотя в строках 2-6 этого кода есть циклы, новое пространство не выделяется, поэтому пространство этого кода равно сложность в основном зависит от первой строки, то есть S(n) = O(n)
Памятка по сложности
источник:Лиам Боится/20/06/2016/…адрес источника:www.bigocheatsheet.com/
легенда
Кривая сложности Big-O
Операционная сложность абстрактных структур данных
сортировка массива
Операции с графами
операции с кучей
Ссылаться на
«Структура данных Dahua»zhuanlan.zhihu.com/p/50479555