В процессе программирования одной из проблем, с которыми обычно приходится сталкиваться, является узкое место в производительности. Много раз рассматривается вопрос о том, как выполнить горизонтальное расширение, но игнорируется самый основной вопрос: действительно ли система достигла узкого места? Узкие места в производительности обычно проявляются в чрезмерном потреблении ресурсов и недостаточной производительности внешней системы обработки или в низком потреблении ресурсов, но скорость отклика программы все еще не соответствует требованиям. И способ настройки
Ищите код, который чрезмерно потребляет ресурсы, и ищите причины и код, которые недоиспользуют ресурсы, но выполнение программы замедляется.Основание определяет высотуВозьмем для сравнения автомобиль.Обычно вы не понимаете принципы работы коробок передач и двигателей, но все же можете водить.Тот же человек, который не понимает структуры данных и алгоритмы, может еще и программировать. Многие думают, что базовые структуры данных и операции инкапсулированы в языки высокого уровня, а библиотечные функции можно вызывать напрямую, так нужно ли изучать структуры данных?
数据结构+算法＝程序
Обычно в программе, сталкиваясь с практической проблемой, полностью используют структуру данных, эффективно сохраняют данные и взаимосвязь между ними в компьютере, а затем выбирают соответствующую стратегию алгоритма и эффективно реализуют ее с помощью программы. способ повысить производительность программы Основной способ.
Как эффективно хранить данные, какую алгоритмическую сложность создают различные структуры данных и существует ли лучший метод хранения для повышения эффективности алгоритма?
Если у вас нет соответствующих знаний, как выполнить вышеуказанную реализацию? Если он отделен от исходного вызова, как завершить эффективную реализацию программы? И все реализации приложений зависят от основы, которая представляет собой структуру данных и алгоритм. Только поняв это, мы можем быть свободны от любой технологической эволюции. Все говорят, что основание определяет высоту!
Базовые концепты
Структура данных представляет собой хранение и организацию данных в компьютере, в основном описывая взаимосвязь между элементами данных и их расположением. Выбор подходящей структуры данных может повысить эффективность выполнения (временная сложность) и эффективность хранения (пространственная сложность) компьютерных программ.
数据结构的三种层次:
Логическая структура — уровень абстракции:Он в основном описывает логическую связь между элементами данных.
集合结构（集）:Все элементы принадлежат совокупности и не имеют никакого другого отношения, кроме принадлежности к одному и тому же множеству. Структура коллекции не подчеркивает никакой ассоциативности между элементами.
线性结构（表）:Между элементами данных существует контекстная связь один к одному. В структуре должен быть уникальный первый элемент и уникальный завершающий элемент.
树形结构（树）:Связь «один ко многим» между элементами данных
网状结构（图）:Существует связь «многие ко многим» между элементами данных в графе или сетевой структуре.
Физическая структура — уровень хранения:Он в основном описывает позиционные отношения между элементами данных.
顺序结构:Последовательная структура заключается в использовании группы последовательных единиц хранения для последовательного хранения логически смежных элементов. 优点:Вам нужно только подать заявку на пространство памяти для хранения самих данных, поддерживать доступ по индексу, а также можно добиться произвольного доступа. 缺点:Непрерывное пространство должно выделяться статически, а использование пространства памяти относительно низкое. Вставка или удаление может потребовать перемещения большого количества элементов, что неэффективно.
链式结构:Цепная структура хранения не использует непрерывное пространство для хранения элементов структуры, а создает узел для каждого элемента. Помимо хранения самих данных, узел также должен хранить указатель на следующий узел. 优点:Неиспользование непрерывного пространства хранения приводит к высокому использованию пространства памяти, преодолевая недостаток прогнозирования количества элементов в последовательной структуре хранения.
При вставке или удалении элементов нет необходимости перемещать большое количество элементов. 缺点:Дополнительное пространство требуется для выражения логической связи между данными,
Доступ по подписке и произвольный доступ не поддерживаются.
索引结构:В дополнение к установлению информации об узлах хранения также создается дополнительная индексная таблица для маркировки адресов узлов. Индексная таблица состоит из нескольких индексных записей. 优点:Номер индекса узла используется для определения адреса хранения узла и извлечения блока скорости. `Минусы:Добавление дополнительной индексной таблицы потребует больше места для хранения.
散列结构:Адрес хранения узла определяется значением ключа узла. Помимо использования для поиска, хеширование также может использоваться для хранения. 优点:Хеширование является развитием метода хранения массива.Некоторые элементы хранимого массива используются в качестве входных данных функции сопоставления.Выводом функции сопоставления является место хранения данных.По сравнению с массивом скорость доступа к данным хэша выше, чем у массива. 缺点:Сортировка не поддерживается и обычно требует больше места, чем при использовании линейной таблицы, а ключи записей не могут повторяться.
Операционная структура - уровень реализации:Основное описание - как реализовать структуру данных
Не существует конкретных правил относительно того, какую физическую структуру принимает каждая логическая структура. Когда структура имеет только одно определение в логической структуре, но есть два варианта в физической структуре, тогда структура принадлежит логической структуре;
сравнение структур данных
Часто используемые структуры данных:
Выбор структуры данных:
О символ
O выражает временную сложность алгоритма, что очень полезно при анализе сложности алгоритма. Общие:
O(1): Наименьшая сложность, независимо от количества данных, затраты времени остаются прежними, и могут быть получены после одного расчета. Алгоритм хеширования обычно O (1)
O(n): Линейный, n представляет количество данных, эквивалент увеличивается, затраты времени также увеличиваются, есть общие алгоритмы обхода
O(n²): Квадрат, это означает, что время занимает квадрат, умноженный на n, когда вы видите встроенный цикл цикла, в основном этот алгоритм является квадратным уровнем, например: пузырьковая сортировка и т. д.
O(log n): логарифмический, обычноx= n, то число x называется логарифмом числа n по основанию a, то есть x=logan, где a обычно равно 2, например: число увеличивается в 8 раз, а потребление времени увеличивается только в 3 раза.Двоичный поиск представляет собой логарифмический алгоритм, и каждый раз отсеивается половина
O(n log n): Линейный логарифм, то есть n раз log n. Согласно приведенным выше данным, данные увеличиваются в 8 раз, а потребление времени составляет 8 * 3 = 24 раза. Сортировка слиянием - это линейный логарифмический алгоритм.
Array
В Java массив используется для хранения коллекции данных одного и того же типа.Обратите внимание, что могут храниться данные только одного типа.
public class Array {
private int[] intArray;
private int elems;
private int length;
public Array(int max) {
length = max;
intArray = new int[max];
elems = 0;
}
/**
* 添加
* @param value
*/
public void add(int value){
if(elems == length){
System.out.println("error");
return;
}
intArray[elems] = value;
elems++;
}
/**
* 查找
* @param searchKey
* @return
*/
public int find(int searchKey){
int i;
for(i = 0; i < elems; i++){
if(intArray[i] == searchKey)
break;
}
if(i == elems){
return -1;
}
return i;
}
/**
* 删除
* @param value
* @return
*/
public boolean delete(int value){
int i = find(value);
if(i == -1){
return false;
}
for (int j = i; j < elems-1; j++) {
//后面的数据往前移
intArray[j] = intArray[j + 1];
}
elems--;
return true;
}
/**
* 更新
* @param oldValue
* @param newValue
* @return
*/
public boolean update(int oldValue,int newValue){
int i = find(oldValue);
if(i == -1){
return false;
}
intArray[i] = newValue;
return true;
}
/**
* 显示所有
*/
public void display(){
for(int i = 0 ; i < elems ; i++){
System.out.print(intArray[i]+" ");
}
System.out.print("\n");
}
/**
* 冒泡排序
* 每趟冒出一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已冒出)
*/
public void bubbleSort(){
for(int i = 0; i < elems-1; i++){//排序趟数 n-1次就行了
System.out.println("第"+(i+1)+"趟：");
for(int j = 0; j < elems-i-1; j++){//每趟次数 (n-i) -1是防止下标越界，后面赋值用到了+1
if(intArray[j] > intArray[j+1]){ //控制按大冒泡还是按小冒泡
int temp = intArray[j];
intArray[j] = intArray[j+1];
intArray[j+1] = temp;
}
display();
}
}
}
/***
* 选择排序
* 每趟选择一个最大数/最小数
* 每次运行数量：总数量-运行的趟数(已选出)
*/
public void selectSort(){
for(int i = 0; i < elems-1; i++) {//排序趟数 n-1次就行了
int min = i;
for(int j = i+1; j < elems; j++){ //排序次数 每趟选择一个数出来，-1次
if(intArray[j] < intArray[min]){
min = j;
}
}
if(i != min ){
int temp = intArray[i];
intArray[i] = intArray[min];
intArray[min] = temp;
}
display();
}
}
/**
* 插入排序
* 每趟选择一个待插入的数
* 每次运行把待插入的数放在比它大/小后面
*/
public void insertSort(){
int j;
for(int i = 1; i < elems; i++){
int temp = intArray[i];
j = i;
while (j > 0 && temp < intArray[j-1]){
intArray[j] = intArray[j-1];
j--;
}
intArray[j] = temp;
}
display();
}
public static void main(String[] args) {
Array array = new Array(10);
array.add(6);
array.add(3);
array.add(8);
array.add(2);
array.add(11);
array.add(5);
array.add(7);
array.add(4);
array.add(9);
array.add(10);
// array.bubbleSort();
// array.selectSort();
array.insertSort();
// array.display();
// System.out.println(array.find(4));
// System.out.println(array.delete(1));
// array.display();
// System.out.println(array.update(2,6));
// array.display();
}
}
Stack
Стек (стек) также известен как стек или стек.Являясь структурой данных, стек хранит данные по принципу «первым пришел, последним вышел». в верхней части стека.
Stack в Java — это подкласс Vector, который определяет только конструктор по умолчанию для создания пустого стека.
Стек — это набор элементов, который состоит из двух основных операций: операция push может использоваться для помещения элементов в стек, а операция pop может удалить верхний элемент из стека.
Следуйте принципу «последним пришел – первым ушел» (LIFO).
временная сложность:
показатель:O(n)
поиск:O(n)
вставлять:O(1)
Удалить:O(1)
Stack()
StackРеализация моделирования
public class Stack {
//小贴士：通常可以利用栈实现字符串逆序，还可以利用栈判断分隔符是否匹配，如<a[b{c}]>，可以正进反出，栈为空则成功。
/**基于数组实现的顺序栈，连续存储的线性实现，需要初始化容量**/
//固定数据类型
//private int[] array;
//动态数据类型
private Object[] objArray;
private int maxSize;
private int top;
public Stack() {
}
public Stack(int maxSize) {
if(maxSize > 0){
objArray = new Object[maxSize];
this.maxSize = maxSize;
top = -1;
}else{
throw new RuntimeException("初始化大小错误：maxSize=" + maxSize);
}
}
/**
* 入栈
* @param obj
*/
public void objPush(Object obj){
//扩容
grow();
//++在前表示先运算再赋值，优先级高，在后表示先赋值再运算，优先级低
objArray[++top] = obj;
}
/**
* 出栈
* @return
*/
public Object objPop(){
Object obj = peekTop();
//声明原顶栈可以回收空间(GC)
objArray[top--] = null;
return obj;
}
/**
* 查看栈顶
* @return
*/
public Object peekTop(){
if(top != -1){
return objArray[top];
}else{
throw new RuntimeException("stack is null");
}
}
/**
* 动态扩容
*/
public void grow(){
// << 左移运算符，1表示乘以2的1次方
if(top == maxSize-1){
maxSize = maxSize<<1;
objArray = Arrays.copyOf(objArray,maxSize);
}
}
/**基于链式存储，不连续存储的非线性实现**/
private class Node<Object>{
private Object data;
private Node next;
public Node(Object data, Node next) {
this.data = data;
this.next = next;
}
}
private Node nodeTop;
private int size;
public void nodePush(Object obj){
//栈顶指向新元素，新元素的next指向原栈顶元素
nodeTop = new Node(obj,nodeTop);
size++;
}
public Object nodePop(){
Node old = nodeTop;
//声明原顶栈可以回收空间(GC)
old.next = null;
//栈顶指向下一个元素
nodeTop = nodeTop.next;
size--;
return old.data;
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder("[ ");
for(Node<Object> node = nodeTop; node != null; node = node.next){
sb.append(node.data.toString() + " ");
}
return sb.toString()+"]";
}
public static void main(String[] args) {
// Stack stack = new Stack(1);
// stack.objPush("abc");
// stack.objPush(123);
// stack.objPush("de");
// stack.objPush("cd");
// stack.objPush("er");
// stack.objPush("hello");
// stack.objPush(666);
// stack.objPush(545);
// stack.objPush("word");
// while (stack.top != -1){
// System.out.println(stack.objPop());
// }
// System.out.println(stack.peekTop());
Stack stack = new Stack();
stack.nodePush("111");
stack.nodePush("222");
stack.nodePush("aaa");
stack.nodePush("bbb");
System.out.println(stack);
while (stack.size > 1)
System.out.println(stack.nodePop());
System.out.println(stack);
}
}
Queue
Очередь — это набор элементов, состоящий из двух основных операций: операция постановки в очередь может использоваться для вставки элементов в очередь, а операция удаления из очереди может использоваться для удаления элементов из очереди.
Следуйте принципу «первым пришел – первым ушел» (FIFO).
Связанный список представляет собой линейный набор узлов, и каждый узел может использовать указатели для указания на другие узлы. Это структура данных, содержащая несколько узлов, которые можно использовать для представления последовательностей.
单向链表: узлы в связанном списке указывают только на следующий узел, а последний узел указывает на ноль.
双向链表: где каждый узел имеет два указателя p, n, так что p указывает на предыдущий узел, а n указывает на следующий узел; указатель n последнего узла указывает на ноль.
循环链表: связанный список, в котором каждый узел указывает на следующий узел, а последний узел указывает на первый узел.
Бинарное дерево (состоит из корневого узла и двух непересекающихся левого и правого поддеревьев, называемых корневыми узлами)
Двоичное дерево — это древовидная структура данных, в которой каждый узел содержит не более двух узлов: левый дочерний узел и правый дочерний узел.
满二叉树: Каждый узел в дереве содержит только 0 или 2 узла.
完美二叉树（Perfect Binary Tree）: Каждый листовой узел в бинарном дереве имеет двух дочерних узлов одинаковой высоты.
完全二叉树: За исключением последнего слоя, количество узлов на каждом слое достигает максимального значения, на последнем слое отсутствуют только несколько узлов справа.Binary TreeКрасно-черное дерево (пять элементов на узел, цвет (если узел красный, то оба его потомка черные), ключ, левый дочерний элемент, правый байт, родитель)
Heap
Куча (также известная как приоритетная очередь (очередь + правило сортировки), максимальная куча на рис. 1, минимальная куча на рис. 2)
Куча — это специальная древовидная структура данных, которая удовлетворяет определенным характеристикам.Значения ключей всех родительских и дочерних узлов во всей куче будут удовлетворять одному и тому же условию сортировки. Куча может быть более точно разделена на максимальную кучу и минимальную кучу.В максимальной куче значение ключа родительского узла всегда больше или равно значению дочернего узла, а максимальное значение во всей куче хранится в корневом узле, а в минимальной куче — родительском. Значение ключа узла всегда меньше или равно значению ключа его дочерних узлов, а минимальное значение во всей куче хранится в корневом узле. .
временная сложность:
Доступ макс/мин:O(1)
вставлять:O(log(n))
Удалить макс/мин:O(log(n))
Hashing
Хэш может отображать данные произвольной длины в данные фиксированной длины. Хеш-функция возвращает хеш-значение.Если два разных ключа получают одинаковое хеш-значение, это явление называется коллизией.
Hash Map: Hash Map — это структура данных, которая может устанавливать отношения между ключами и значениями.Hash Map может использовать хэш-функции для преобразования ключей в индексы в сегментах или слотах, тем самым оптимизируя скорость поиска целевых значений.
разрешение коллизий
链地址法（Separate Chaining）: в методе цепных адресов каждая корзина независима друг от друга и содержит список ряда индексов. Временная сложность операции поиска представляет собой сумму времени поиска в корзине (фиксированное время) и времени прохождения списка.
开地址法（Open Addressing）: В методе открытых адресов, когда вставляется новое значение, будет оцениваться, существует ли хэш-сегмент, соответствующий значению.Если он существует, следующее возможное местоположение будет выбрано по очереди в соответствии с определенным алгоритмом до тех пор, пока не будет незанятого адреса находится. Так называемый метод открытого адреса также означает, что местоположение элемента не всегда определяется его хеш-значением.
Hashing
Graph
Граф — это абстрактный тип данных, состоящий из отношения «многие ко многим» между элементами данных и набора основных операций.
无向图（Undirected Graph）: неориентированный граф имеет симметричную матрицу смежности, поэтому, если есть ребро от узла u до узла v, также есть ребро от v до u.
有向图（Directed Graph）: Матрица смежности ориентированного графа асимметрична, т. е. если есть ребро от u до v, это не означает, что должно быть ребро от v до u.
Graph
алгоритм
Сортировать
быстрая сортировка
Стабильный: Нет
временная сложность:
Лучшее время:O(nlog(n))
Худшее время:O(n^2)
Среднее время:O(nlog(n))
Quicksort
Сортировка слиянием
Сортировка слиянием — это типичный алгоритм «разделяй и властвуй», который непрерывно делит массив на две части, сортирует левый подмассив и правый подмассив соответственно, а затем объединяет два массива в новый отсортированный массив.
Стабильный: да
временная сложность:
Лучшее время:O(nlog(n))
Худшее время:O(nlog(n))
Среднее время:O(nlog(n))
сортировка ведра
Сегментная сортировка делит массив на конечное число сегментов. Затем каждое ведро сортируется индивидуально (возможно, с использованием другого алгоритма сортировки или рекурсивно продолжает использовать сортировку ведра для сортировки).
временная сложность:
Лучшее время:Ω(n + k)
Худшее время:O(n^2)
Среднее время:Θ(n + k)
Bucket Sort
сортировка по основанию
Поразрядная сортировка похожа на сортировку ведрами, которая делит массив на ограниченное количество ведер, однако не сортирует каждое ведро отдельно после деления, а напрямую объединяет.
временная сложность:
Лучшее время:Ω(nk)
Худшее время:O(nk)
Среднее время:Θ(nk)
Алгоритмы графов
поиск в глубину
Алгоритм поиска в глубину — это алгоритм, который сначала обходит дочерние узлы, а не откатывается.
временная сложность:O(|V| + |E|)
DFS / BFS Traversal
Поиск в ширину
Поиск в ширину — это алгоритм обхода графа, который преимущественно обходит соседние узлы, а не дочерние узлы.
временная сложность:O(|V| + |E|)
DFS / BFS Traversal
топологическая сортировка
Топологическая сортировка — это линейная сортировка узлов ориентированного графа.Если существует ребро от u до v, считается, что нижний индекс u находится перед v.
временная сложность:O(|V| + |E|)
Алгоритм Дейкстры
Алгоритм ДейкстрыДля решения задачи поиска кратчайшего пути с одним источником в ориентированных графах.
временная сложность:O(|V|^2)
Dijkstra's
Алгоритм Беллмана-Форда
**Bellman-Ford 算法** — алгоритм расчета кратчайшего пути от одной исходной точки до других узлов взвешенного графа.
Хотя алгоритм сложнее, чем алгоритм Дейкстры, он подходит для графов, содержащих отрицательные ребра.
временная сложность:
Лучшее время:O(|E|)
Худшее время:O(|V||E|)
Bellman-Ford
Алгоритм Флойда-Уоршалла
Floyd-Warshall 算法Может использоваться для поиска кратчайшего пути к любому узлу в ациклическом взвешенном графе.
временная сложность:
Лучшее время:O(|V|^3)
Худшее время:O(|V|^3)
Среднее время:O(|V|^3)
Основной алгоритм
**Prim 算法** — жадный алгоритм вычисления минимального остовного дерева во взвешенном неориентированном графе. Другими словами, алгоритм Прима может извлекать подмножество ребер с минимальной стоимостью, соединяющих все узлы в графе.
временная сложность:O(|V|^2)
Prim's Algorithm
Алгоритм Крускала
**Kruskal 算法**Это также алгоритм вычисления минимального остовного дерева графа.Отличие от Prim в том, что граф не должен быть связным.
временная сложность:O(|E|log|V|)
Kruskal's Algorithm
битовая операция
Битовая операция — это технология работы на битовом уровне, и правильная битовая операция может помочь нам увеличить скорость работы и уменьшить использование памяти.