- двумерный массив
- граф представляют в виде матрицы смежности
- вершины — столбцы и строчки
- есть путь — на перекрестие ставится 1
- нет пути — на перекрестии ставится 0
Рубрики
Рубрика: Основы Программирования
Рубрики
Графы «понятие»
- абстрактная структура данных
- представляет множество вершин
- набор рёбер — соединений между пару вершин
Пример
карта — города(вершины), которые соединены маршрутами (ребрами)
Какие бывают РЕБРА
- однонапраленные
идут слева на направа, а обратно мы возвращаться не можем - двунаправленные
из A в B и B в A можем попасть
рекурсия — это функция, которая вызывает сама себя
должна иметь случай или условие, при котором
Требование
функция прекращается иначе будет переполнение стека вызова (функция будет вызывать сама себя бесконечно)
Примеры
- факториал
следующие
5!=1*2*3*4*5;
const factorial = (n) => {
if (n === 1) {
return 1
}
return n*factorial(n-1);
}
console.log(factorial(5))- числа фибоначи
последующее число равняется сумме предыдущих чисел
1,1,2,3,5,8,13,21
const fibonachi = (n) => {
if (n === 1 || n ===2){
return 1
}
return fibonachi(n-1) + fibonachi(n-2)
}
console.log(fibonachi(5))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);O(n*n)
Не эффективная сортировка
- пробегаемся по всему массиву и сравниваем попарно лежащие элементы.
- Если следующий элемент массива меньше чем предыдущий, то мы меняем их местами и получается в своего рода всплытие — самый большой элемент потихоньку всплывает наверх
const arr=[1,4,5,8,51,2,7,5,5,2,11]//[0,1,1,2,3....]
let cnt=0;
function bubleSort(arr){
for (let i = 0; i< arr.length;i++){
for (let j = 0; j < arr.length; j++){
if(arr[j+1] < arr[j]){
let tmp = arr[j]
arr[j] = arr[j+1]
arr[j+1] = tmp
}
cnt+=1
}
}
return arr;
}
console.log('length',arr.length);
console.log(bubbleSort(arr))
console.log('count=',cnt)