рекурсивная структура данных
каждый узел данных является так же деревом, но для данного дерева каждый узел является поддеревом
класс бинарного дерева
Задача
надо обойти каждый узел и посчитать сумму значений, который хранить каждый из этих узлов
Рубрика: Алгоритмы
ВАЖНО
во избежание вычисления каких либо повторных функций
- повторное использование за ранее вычисленных данных
- использование вычислительных ресурсов
(хранение в памяти)
не важно
длительный этот путь или нет, а самое
главное
количество пройденных участков или существует ли путь
ЗАДАЧА
Найти путь из точки A в точку B за минимальное количество шагов
Процесс решения
задаём для каждой вершины название
создаём объект, который содержит вершины (содержит путь к точке B)
используется Cтруктура Данных «очередь»
- состоит из каких то элементов
- элементы всегда добавляются в конец структуры, а извлекаются из её начала
- тот кто пришел на кассу первым — уходит первым
- тот кто пришел на кассу последним — уходит последним
- FIFO — FIRST IN FIRST OUT
алгоритм поиска кратчайшего пути в графе
Важно
учитывается длинна пройденного ребра — вес
Задача
стартовая точка A
конечная точка G
A—B—F—G
| / |
| / |
| / |
| D |
| / |
| / |
|/ |
C——E
составляется таблица, на котором на первом этапе записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные вершины являются не достижимыми и мы их помечаем знаком бесконечности.
На втором этапе мы помечаем эти (B и C) вершины как рассмотренные,
На третьем этапе мы рассматриваем вершины, на которые мы можем попасть из точек B и C и в таблице записываем значения из точки A до точек, которые мы достигаем из вершин B и С. Опять же помечаем эти точки, как уже рассмотренные.
На следующем этапе мы достигаем конечной точки G, но у нас происходит перерасчет (мы находим путь до F, до которого оказывается короче и перезаписываем значение в таблице).
И на следующем этапе мы проделываем тоже самое и находим самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за пять условных единиц.
O(log2n*n)
самый быстрый
разделяй и властвуй
делим массив на подмассивы и каждый раз рекурсивно
мы выбираем опорный элемент у каждого массива
его можно выбрать случайно, но часто центрально
пробегаемся по массиву и все элементы, которые меньше опорного, добавляем в один массив, все которые больше, добавляем в другой массив.
После такой операции у нас получается два массива
(с меньшими числами и с большими числами чем опорные).
Для каждого из этих массивов выполняется точно такая же операция. В каждой из этих массивов выбирается опорный элемент и происходит сортировка и так происходит до тех пор, пока длина массива становится равна единице (именно это условие и будет базовым случаем выхода из рекурсии).
И после этих операций эти маленькие массивы склеиваются в один большой.
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function quickSort(arr){
if (arr.length<=1){
return arr
}
let pivotIndex = Math.floor(arr.length/2);
let pivot=arr[pivotIndex]
let less=[]
let greater=[]
for(let i=0;i<arr.length;i++){
cnt+=1
if(i===pivotIndex)
continue;
if(arr[i]<pivot){
less.push(arr[i])
} else {
greater.push(arr[i])
}
return [...quickSort(less),pivot,...quickSort(greater)]
}
console.log(quickSort(arr))
console.log(cnt);