Структура данных — Хранение + Организация + Группировка для эффективного использования данных. — Данные-видео, изображения, аудио, текст, геопространственные….
Массивы. Набор элементов одного типа. Теперь мы видим реализацию всех видов операций над массивами и сколько времени тратится на каждую т.е. временную сложность
Поиск:
- Линейный
- Бинарный
Линейный поиск — чтобы проверить, существуют ли элементы в данном массиве, и если существуют, то положение этого элемента.
В этом мы просто перебираем весь массив и проверяем каждый элемент с заданным вводом (значением), и, если он существует, просто отображаем позицию. Таким образом, временная сложность для линейного поиска будет такой:
Лучший случай: O(1), если первый элемент в массиве является совпадающим элементом.
Наихудший случай: O(n), если последний элемент в массиве является совпадающим элементом. Здесь n — размер массива. Поэтому мы можем сказать, что для наихудшего случая временная сложность прямо пропорциональна размеру массива.
Двоичный поиск — чтобы проверить, существует ли элемент в данном массиве, и если существует, то положение этого элемента эффективным способом (минимальная временная сложность). Работает только для отсортированных массивов.
В этом мы разделим массив на 2 половины и возьмем разделенный массив как отдельный массив. Если искомый элемент существует в правой части массива, то мы отбрасываем левый и продолжаем повторять деление и поиск в правой половине, и наоборот, если элемент существует в левой половине. Также есть еще один случай, когда мы можем найти элемент посередине, что будет лучшим случаем.
Теперь мы видим реализацию бинарного поиска в Javascript:
const A = [1, 24, 32 , 87, 90];
const BinarySearch = (A, element) => {
let start = 0;
let end = A.length - 1;
while (end >= start) {
let mid = parseInt((start + end) / 2);
if (A[mid] === element) {
return mid;
} else if (element < A[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return -1;
}
console.log(BinarySearch(A, 87));
Временная сложность в бинарном поиске:
Лучший случай:O(1) — если элемент присутствует в середине.
Худший случай: O(log(n)) — если нам нужно снова и снова делить массив на маленькие массивы.
n + n/2 + n/4 + n/8 + n/16 …. = 2 / n^k
k = log(n) — сложность наихудшего случая
При вычислении середины, чтобы выполнить операцию изящно, мы можем использовать low + (high-low) / 2, чтобы избежать эффектов, если размер массива очень велик, и сумма low + high может превышать максимальный диапазон. . В javascript это 2⁵³ -1.
Рекурсивный способ написания бинарного поиска:
const A = [1, 24, 32 , 87, 90];
const BinarySearch = (A, element, start, end) => {
if (end < start) {
return -1;
}
let mid = parseInt ((start + end) / 2);
if (element === A[mid]) {
return mid;
} else if (A[mid] > element) {
BinarySearch(A, element, start, mid -1);
} else {
BinarySearch(A, element, mid + 1, end);
}
}
BinarySearch(A, 87, 0, 4);
Получение первого и последнего вхождений числа в массиве с помощью двоичного поиска:
Первое появление элемента в массиве:
const A = [1, 87, 87 , 87, 90];
const FirstOccurrence = (A, element) => {
let start = 0;
let end = A.length - 1;
let result = -1;
while (end >= start) {
let mid = parseInt((start + end) / 2);
if (A[mid] === element) {
result = mid;
end = mid -1;
} else if (element < A[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return result;
}
console.log(FirstOccurrence(A, 87));
Последнее вхождение элемента в массив:
const A = [1, 87, 87 , 87, 90];
const LastOccurrence = (A, element) => {
let start = 0;
let end = A.length - 1;
let result = -1;
while (end >= start) {
let mid = parseInt((start + end) / 2);
if (A[mid] === element) {
result = mid;
start = mid + 1;
} else if (element < A[mid]) {
end = mid - 1;
} else {
start = mid + 1;
}
}
return result;
}
console.log(LastOccurrence(A, 87));
В приведенном выше примере 2 мы видим — для первого вхождения, даже если мы найдем элемент, мы будем продолжать обход с левой стороны, чтобы получить первое вхождение, и последнее вхождение, мы продолжим обход справа сторона, чтобы получить последнее вхождение.
Подсчет всех вхождений элементов с использованием бинарного поиска: —это просто комбинация двух вышеперечисленных кодов, которая приводит временную сложность к log(n) по сравнению с N.
Сортировка:
Сортировка выбором: нестабильный алгоритм сортировки
При этом мы сравним весь элемент со всеми последующими элементами, и если этот элемент больше, чем последующие элементы, мы поменяем элементы местами. При таком подходе при первом проходе мы получим наименьший элемент на первом месте. При таком подходе левая часть массива всегда сортируется.
Исходный массив: 3, 1, 8, 7, 2, 20
Проход 1: [ 1, 3, 8, 7, 2, 20 ]
Проход 2: [ 1, 2, 8, 7, 3, 20 ]
Проход 3: [ 1, 2, 3, 7 , 8, 20 ]
Проход 4: [ 1, 2, 3, 7, 8, 20 ]
Проход 5: [ 1, 2, 3, 7, 8, 20 ]
Проход 6: [ 1, 2, 3, 7, 8, 20 ] — Выход
function selectionSort(arr) {
try {
const n = arr.length;
for (let i =0 ; i < n-1; i++) {
let iMin = i;
for (let j = i + 1 ; j<= n -1 ; j++) {
if (arr[iMin] > arr[j]) {
iMin = j;
}
}
let temp = arr[i];
arr[i] = arr[iMin]
arr[iMin] = temp;
}
console.log(arr);
} catch (e) {
console.log(e);
throw e;
}
}
selectionSort([3, 1, 8, 7, 2, 20])
Output: [ 1, 2, 3, 7, 8, 20 ]
Сложность: O(n²)
Пузырьковая сортировка: стабильный алгоритм сортировки
При этом мы будем сравнивать каждый элемент с соседним элементом в каждом проходе, и если элемент больше, мы поменяем местами. Таким образом, с каждым проходом мы получаем отсортированную правую часть массива (например, последний элемент в первом проходе и последующих). В этом типе сортировки мы получаем самые большие элементы, отсортированные в конце массива, в отличие от сортировки выбором, в которой мы получаем самый маленький элемент в начале массива (также отсортированный).
Массив: [1, 3, 7, 2, 8, 20]
Прохождение 1: [1, 3, 7, 2, 8, 20]
Pass2: [1, 3, 2, 7, 8, 20]
Pass3: [1, 2, 3, 7, 8, 20]
Pass4: [1, 2, 3, 7, 8, 20]
Pass5: [1, 2, 3, 7, 8, 20]
Pass6: [1, 2, 3, 7, 8, 20] — Выход
function BubbleSort(arr) {
try {
const n = arr.length;
for (let i = 0; i < n; i++) {
for (let j = 0; j <= n-2 - i; j++) {
if (arr[j] > arr[j+1]) {
let temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
console.log(arr);
} catch (e) {
throw e;
}
}
BubbleSort([3, 1, 8, 7, 2, 20])
Output: [ 1, 2, 3, 7, 8, 20 ]
Сложность: O(n²)
Оптимизация вышеуказанного алгоритма для сокращения времени работы:
- Вместо того, чтобы запускать внутренний цикл для n-2 , мы можем запустить его до n -k -1 , поскольку мы знаем, что правая часть сортируется на каждой итерации.
- Предположим, что если массив уже отсортирован, то мы уменьшаем, принимая счетчик = 0 во внешнем цикле, и когда выполняется какой-либо обмен, мы меняем значение как счетчик = 1, и после каждой итерации во внутреннем цикле, если значение равно 0, это означает, что обмен не выполняется, поэтому массив уже отсортировано.
Сортировка вставками: стабильный алгоритм сортировки
В этом алгоритме мы начинаем со 2-го значения массива, затем сравниваем значения со всеми крайними левыми значениями до тех пор, пока весь массив не будет итерирован или если значение слева меньше значения, которое мы сравниваем.
Входной массив: [9,8,7,2,3,4,5]
Pass1: [ 8, 9, 7, 2, 3, 4, 5 ]
Pass2: [ 7, 8, 9, 2, 3, 4, 5 ]
Pass3: [ 2, 7, 8 , 9, 3, 4, 5 ]
Проход 4: [ 2, 3, 7, 8, 9, 4, 5 ]
Проход 5: [ 2, 3, 4, 7, 8, 9, 5 ]
Pass6: [ 2, 3, 4, 5, 7, 8, 9 ] — Выход
function InsertionSort(arr) {
try {
const n = arr.length;
for (let i = 1; i< n; i++) {
let temp = arr[i];
let index = i;
while(index && arr[index-1] > temp) {
arr[index] = arr[index-1];
index --;
}
arr[index] = temp;
}
console.log(arr);
} catch (e) {
throw e;
}
}
InsertionSort([9,8,7,2,3,4,5])
Output: [ 2, 3, 4, 5, 7, 8, 9 ]
Сложность: O(n) — лучший вариант уже отсортирован
O(n²) — наихудший случай
Сортировка слиянием: стабильный алгоритм сортировки:разделяй и властвуй. Разделите большой массив на несколько меньших списков (пока в каждом списке будет только один элемент), а затем отсортируйте их и объедините обратно. Здесь мы будем использовать рекурсию.
function mergeSortedArrays(leftArray, rightArray, arr) {
try {
let n1 = leftArray.length;
let n2 = rightArray.length;
let counter1 = 0, counter2 = 0, j =0;
while(counter1 < n1 && counter2 < n2) {
if (leftArray[counter1] > rightArray[counter2]) {
arr[j++] = rightArray[counter2++];
} else if (leftArray[counter1] < rightArray[counter2]) {
arr[j++] = leftArray[counter1++];
} else {
arr[j++] = rightArray[counter2++];
arr[j++] = leftArray[counter1++];
}
}
while(counter1 < n1) {
arr[j++] = leftArray[counter1++];
}
while(counter2 < n2) {
arr[j++] = rightArray[counter2++];
}
} catch (e) {
throw e;
}
}
function MergeSort(arr) {
try {
let result = [];
let n = arr.length;
if (n < 2) {
return arr;
}
let mid = parseInt(n/2);
let leftArray = [];
let rightArray = [];
for (let i = 0; i < mid; i++) {
leftArray.push(arr[i]);
}
for (let i = mid; i<= n-1; i++) {
rightArray.push(arr[i]);
}
MergeSort(leftArray);
MergeSort(rightArray);
mergeSortedArrays(leftArray, rightArray, arr)
} catch (e) {
throw e;
}
}
const A = [9,3,2,1,0];
MergeSort(A)
console.log(A);
Output: [ 0, 1, 2, 3, 9 ]
Временная сложность: O(nlogn) — наихудший случай
Сортировка слиянием (слева): T (n/2)
Сортировка слиянием (справа): T (n/2)
Слияние: cT(n)
Другое выполнение займет некоторое постоянное время = c
Итого = 2T(n/2) + cT(n) + константа1 = ~ O(nlogn) = 2^K T(n/2^k) + kconstan = (n/ 2^k =1)
Пространственная сложность: O(n) [используется для сохранения результатов слияния]
Всего уровней: log(n)
Код:https://github.com/rishabhjj/Datastructure_Algorithm/tree/master/Array
В случае каких-либо вопросов и предложений свяжитесь со мной https://www.linkedin.com/in/rishabh-jain-a5978583/ или отправьте письмо по адресу @[email protected]
