Алгоритмы
Ссылки
youtu.be
Сложность O N
Что такое сложность алгоритма?
- Комбинационная сложность -
минимальное число элементов для
реализации алгоритма в виде
вычислительного устройства.
- Описательная сложность -
длина описания алгоритма на языке
- Вычислительная сложность -
количество элементарных операций,
исполняемых алгоритмом, для неких
вводных данных.
Нет циклов - описательная сложность
почти связанна с вычислительной
Есть циклы - интересна связь
времени вычисления от
входных данных.
Введём параметр N, который влияет на скорость.
Это может быть:
- Размер массива
- Количество символов в строке
- Количество битов в записи числа
- если параметров несколько - то
приблизительный параметр функция
от нескольких параметров
BigO показывает верхнюю границу зависимости между входными параметрами в функцию и количеством операций.
Зависимость меж параметрами и количеством операций..
Найти наибольший общий делитель
function fun(a, b){
while (b !== 0){
remainder = a % b
console.log(`${a} % ${b} = ${remainder}`)
a = b
b = remainder
}
return a
}
fun(10, 15)
// переделал на более короткую запись
// Найти наибольший общий делитель с рекурсией
function fun(a, b){
let remainder = a % b
if ( remainder !== 0 ) return fun(b, remainder)
return b
}
// или от большего отнимать меньшее до тех пор, пока они не станут равны
function fun(a, b){
if(a === b) return a
if(a > b) return fun(b, a-b)
return fun(a, b-a)
}
// Найти наименьшее делимое, при котором не будет остатков
function fun2(a, b){
return a * b / fun(a, b)
}
fun2(20, 25)
Задачка. С массива чисел найти максимальную сумму 2х чисел, используя только 1 перебор
console.clear()
function fun(arr){
let i = arr.length
let max = arr[0], max1 = arr[0]
while(i--){
if(arr[i] > max) max = arr[i]
else if(
arr[i] === max ||
arr[i] > max1
) max1 = arr[i]
}
return max + max1
}
fun([5, 0, 0, 9, 4, 4])
//fun([4, 4, 9, 0, 0, 5])
Написать функцию, которая принимает 2 функции и генерирует график сравнения их эффективности
132
Узнаём, что работает эффективнее
console.clear()
var a, i = 300000000, time = new Date().getTime()
while (i--) a=300*250
console.log(`SecondWay: ${(new Date().getTime()) - time}ms`);
Найти простые множители числа
var fun = function(n){
let arr = [], i = 2
while(i < n){
while(n % i === 0){
arr.push(i)
n = n / i
}
i++
}
if(n > 1) arr.push(n)
return arr
}
console.log(fun(9))
// Оптимально
var fun = function(n){
let arr = [], i = 3
while(n % 2 === 0){
arr.push(i)
n = n / 2
}
while(i < n){
while(n % i === 0){
arr.push(i)
n = n / i
}
i += 2
}
if(n > 1) arr.push(n)
return arr
}
console.log(fun(10))
Бинарный поиск
О сложность или скорость
t время
n количество операций
O(n) n - колич элем в массиве
// Бинарный поиск (данные должны быть отсортированны) O(log2n)
console.clear()
var arr = [];
for(let i = 0; i < 16; arr.push(i), i++);
function binary_search(array, item){
let start = 0,
end = array.length,
middle;
while (start <= end) {
middle = Math.floor((start + end) / 2)
if (array[middle] === item) return middle
if (array[middle] > item) end = middle - 1
else start = middle + 1
}
return -1
}
console.log(binary_search(arr, 4))
// С рекурсией
console.clear()
var arr = [];
for(let i = 0; i < 16; arr.push(i), i++);
function search_binary_recursive(array, item, start, end){
let middle = Math.floor((start + end) / 2)
if (array[middle] === item) return middle
if (start === end) return -1
if (array[middle] > item) return search_binary_recursive(array, item, start, middle - 1)
return search_binary_recursive(array, item, middle + 1, end)
}
console.log(search_binary_recursive(arr, 4, 0, arr.length))
Сортировка выбором
// Сортировка выбором, где находим инимум и ставим в начало O(n*n)
console.clear()
var arr = [8, 12, 752, 105]
function sort_selection(array){
for(let i = 0, k = array.length; i < k; i++){
let index_min = i
for(let i1 = i+1; i1 < k; i1++){
if(array[i1] < array[index_min]) index_min = i1
}
let tmp = array[i]
array[i] = array[index_min]
array[index_min] = tmp
}
return array
}
console.log(sort_selection(arr))
Сортировка пузырьком O(n*n)
// Сортировка Пузырьком
console.clear()
var arr = [8, 12, 752, 105]
function sort_bubble(array){
for(let i = 0, k = array.length; i < k; i++){
for(let i1 = 0; i1 < k; i1++){
if(array[i1 + 1] < array[i1]){
let tmp = array[i1]
array[i1] = array[i1+1]
array[i1+1] = tmp
}
}
}
return array
}
console.log(sort_bubble(arr))
Сортировка quick O(log2n*n) (максимально эффективная)
// Сортировка quick O(log2n*n)
console.clear()
var arr = [8, 12, 752, 105, 15]
function sort_quick(array){
var len = array.length
if(len <= 1) return array
let pivot_index = Math.floor(len / 2)
let pivot = array[pivot_index]
let array0 = [], array1 = []
for(let i = 0; i < len; i++){
if(i === pivot_index) continue
if(array[i] < pivot) array0.push(array[i])
else array1.push(array[i])
}
let array_rt = [];
array_rt = array_rt.concat(sort_quick(array0))
array_rt.push(pivot)
array_rt = array_rt.concat(sort_quick(array1))
return array_rt
}
console.log(sort_quick(arr))
Факториал (числа умноженные до текущего числа)
// Факториал (числа умноженные до текущего числа)
console.clear()
function factorial(n){
if (n === 1) return 1
return n * factorial(n - 1)
}
console.log(factorial(5))
Фибоначи
// Числа фибоначи (где последующее число === сумме 2х предыдущих 1 1 2 3 5 8 13 21)
// Нифига не понял, но формула встречается часто
console.clear()
function fibonachi(n){
if (n === 1 || n === 2) return 1
return fibonachi(n - 1) + fibonachi(n - 2)
}
console.log(fibonachi(8))
Логарифм log
log[a] b = c
они равны
a^c = b
Грубо сколько раз необходимо умножить a само на себя, чтоб получилось b
c - и есть это количество умножений
console.clear()
logarifm = (base, n, count = 0) => {
count++
n = n / base
if (n === 1) return count
return logorifm(base, n, count)
}
console.log(logarifm(5, 25))
console.log(logarifm(2, 8))
Задачка
Одним перебором массива (размером n) переместить m первых элементов в конец, не меняя порядок и не пользуясь сторонними функциями
let arrayToEnd = (n = 10, m = 3) => {
// Create array
let array = Array(n)
.fill()
.map((element, i) => (i+1) + '_element')
console.log(array)
let i = 0,
i_new,
tmp,
tmp_number,
mod = n % m
while (i < n) {
if (i + m >= n)
m = n - i - mod
else
tmp_number = n - i - mod // for balance
i_new = i + m
if (
i <= i_new && // for balance
i_new !== n
)
tmp_number = i // for balance
else
i_new = i
tmp = array[i];
array[i] = array[i_new]
array[i_new] = tmp
console.log({i:i, i_new:i_new})
console.log(array)
i++
}
console.log('Answer:')
console.log(array)
}
arrayToEnd(10, 7)
Задачка
let array = [-3, 0, 1, 3, 4],
k = 5
Определить в массиве, какая сумма 2х чисел даёт k
let array = [-3, 0, 1, 3, 4],
k = 5,
sum_two = (array, k) => {
let tmp = {},
tmp_number;
for (let i = 0, length = array.length; i < length; i++) {
tmp_number = k - array[i]
if (tmp_number in tmp)
return [tmp_number, array[i]]
tmp[array[i]] = 1
}
return tmp
}
sum_two(array, k)
Если он отсортирован, то ищем в этом же массиве array
через бинарный поиск
Если отсортирован, то можно с 2х сторон взять числа и смотреть
если больше, то уменьшать i с правой стороны иначе с начала