мы знаемПрограммы состоят из структур данных и алгоритмов. Среди них структура данных представляет собой организационную форму данных, а базовые структуры данных включают в себя массивы, связанные списки, стеки, очереди, деревья, хеш-таблицы, графы, кучи и т.п. Алгоритмы, с другой стороны, представляют собой способ или процесс манипулирования данными в структуре данных, другими словами, способ решения проблемы. Отношения между ними: структуры данных служат алгоритмам, многие алгоритмы полагаются на определенные структуры данных, но не все алгоритмы, алгоритмы могут быть независимыми от структур данных. В этом выпуске мы поговорим об алгоритмах.
Важность алгоритмов обучения
Прежде чем представить конкретный алгоритм, позвольте мне рассказать об изначальном замысле алгоритма обучения. Мое первоначальное намерение состоит не более чем из двух пунктов: во-первых, BAT и другие интернет-компании должны спрашивать о знании алгоритмов при приеме на работу и собеседовании, если я хочу войти в интернет-компанию, я должен хорошо изучить алгоритмы, для разных сценариев я могу правильно выбрать соответствующую структуру данных и алгоритм, что делает программу более надежной и повышает эффективность работы программы.
Область применения
В настоящее время в каждом подразделении компьютера используются разные алгоритмы. Напримерпоисковый движок, мы обычно используем браузеры, такие как Google и Baidu, пока мы вводим ключевое слово, браузербыстрыйОн возвращает соответствующий набор, и за этим набором скрывается множество алгоритмов. Без этих алгоритмов мы бы не смогли так быстро получить желаемые результаты. Другим примером является искусственный интеллект, который реализует различные сценарии приложений, такие как распознавание человеческого тела и речи, с помощью алгоритмов вычислительной модели.
Анализ алгоритмов
Мы уже ввели, что алгоритм — это метод решения проблемы, и для одной и той же проблемы могут быть разные решения. Поэтому, чтобы измерить плюсы и минусы алгоритма, предложенныйвременная сложностьикосмическая сложностьэти два понятия.
временная сложность
В общем случае количество повторений основных операций в алгоритме является функцией f(n) размера задачи n, а измерение времени алгоритма записывается какT(n) = O(f(n)), что означает, что с увеличением размера задачи n скорость роста времени выполнения алгоритма такая же, как и скорость роста f(n), которая называется асимптотической временной сложностью алгоритма, или временем сложность короче.
космическая сложность
Сложность пространства — это мера размера памяти, временно занимаемой алгоритмом во время выполнения процесса, обозначаемая какS(n)=O(f(n)). Плюсы и минусы алгоритма в основном измеряются по двум аспектам: время выполнения алгоритма и необходимое пространство для хранения.
Алгоритм сортировки
По временной сложности алгоритмы сортировки можно условно разделить на две категории, одна из которых представлена сортировкой выбором.O(n^2)алгоритм, другой представлен быстрой сортировкойO(nlogn)алгоритм. Увидев это, мы не можем не спросить: поскольку существуетO(nlogn)алгоритмы сортировки, т.O(n^2)Алгоритм все еще нужен? Чтобы ответить на этот вопрос, давайте рассмотримO(n^2)Характеристики алгоритма сортировки: во-первых, он относительно прост, кодирование простое и его легко реализовать в некоторых конкретных сценариях.O(n^2)более подходящим, например, на машинном языкеO(n^2)Его проще реализовать; во-вторых, из идеи простого алгоритма сортировки выводятся сложные алгоритмы сортировки, такие как сортировка по Хиллу, являющаяся оптимизацией сортировки вставками; наконец, для некоторых простых алгоритмов в силу их собственных свойств их можно использовать как улучшения в подпроцессе более сложного алгоритма сортировки. Исходя из этого, данная бумагаO(n^2)Двумя репрезентативными алгоритмами в алгоритме сортировки являются алгоритм выбора и алгоритм вставки.
сортировка выбором
Идея: Найти наименьшее значение во всем массиве для сортировки, затем обменять его на первый элемент для сортировки, затем найти наименьший элемент в оставшихся элементах, а затем сравнить его с первым отсортированным элементом на обмен, и так на. Чтобы углубить ваше понимание, возьмите конкретный пример, отсортируйте 8, 6, 2, 3, 1, 5, 7 и 4 в порядке возрастания.
Реализация сортировки выбором на языке Java выглядит следующим образом:
/**
* 思路：每次从待选数组中选择一个最小元素，然后和对应位置交换位置
* @param arr
* @param n
*/
public void sort(int[] arr, int n) {
for(int i=0;i<n;i++) {
// 1. 寻找[i,n)区间里的最小元素
int minIndex = i;
for(int j=i+1;j<n;j++ ) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
// 2. 交换位置
this.swap(arr,i,minIndex);
}
}
Сортировка вставками
Идея: сортировка вставками заключается в вставке одного элемента за раз на основе уже упорядоченной небольшой последовательности. Конечно, в начале эта небольшая упорядоченная последовательность имеет только 1 элемент, который является первым элементом. Сравнение начинается с конца упорядоченной последовательности, то есть элемент, который вы хотите вставить, сравнивается с самым большим из уже упорядоченных, если он больше его, то он будет вставлен сразу после него, в противном случае он будет продолжать поиск, пока не найдет тот, который следует вставить. Если встречается элемент, равный вставленному элементу, вставленный элемент помещает вставляемый элемент после равного элемента. Следовательно, порядок до и после одинаковых элементов не изменился, а порядок вне исходной неупорядоченной последовательности является отсортированным порядком, поэтому сортировка вставками стабильна.
public void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
for( int j = i; j > 0 && arr[j].compareTo(arr[j-1]) < 0 ; j--)
swap(arr, j, j-1);
}
}
Сравнивая реализации кода сортировки выбором и сортировки вставками, мы можем обнаружить, что после сортировки некоторых частей, если вновь вставленное число больше отсортированного максимального значения, его не нужно сравнивать с другими числами.меньше сравнений. но,Следует отметить, что сортировка вставками требует операции замены каждый раз, когда она проходит., эта операция замены состоит из трех операций присваивания, что приводит к увеличению времени сортировки вставками по сравнению с сортировкой выбором. В ответ на эту проблему наши предки придумали метод:Сделайте копию элемента для сравнения, а затем сравнивать с элементами в отсортированном массиве по очереди. Если он меньше, чем элементы в отсортированном массиве, элементы в отсортированном массиве будут перезаписаны сравниваемыми элементами и так далее. Как показано на рисунке ниже, сначала мы делаем копию элемента 6, а затем проверяем, должен ли быть размещен в текущей позиции элемент 6. Сравнивая размер элемента 6 и элемента перед ним, выясняется, что элемент 8 должен быть размещен в позиции элемента 6, поэтому элемент 8 покрывает элемент 6, а затем мы проверяем, должен ли элемент 6 быть помещен в позицию предыдущего элемента.В это время, поскольку элемент 8 находится в 0-й позиции, мы делаем не нужно напрямую покрывать его. Его реализация кода Java выглядит следующим образом:
for (int i = 0; i < n; i++) {
// 寻找元素arr[i]合适的插入位置
Comparable e = arr[i];
int j = i;
for( ; j > 0 && arr[j-1].compareTo(e) > 0 ; j--)
arr[j] = arr[j-1];
arr[j] = e;
}
Таким образом, внутреннему циклу нужно выполнить операцию присваивания только один раз, и эффективность значительно оптимизирована, что не только превышает сортировку выбором, но также может достигать временной сложности доO(n).
Добро пожаловать в общедоступную учетную запись WeChat: Mu Keda, все статьи будут синхронизированы в общедоступной учетной записи.