Алгоритмы

  1. Ссылки
  2. Сложность O N
  3. Найти наибольший общий делитель
  4. Задачка. С массива чисел найти максимальную сумму 2х чисел, используя только 1 перебор
  5. Написать функцию, которая принимает 2 функции и генерирует график сравнения их эффективности
  6. Узнаём, что работает эффективнее
  7. Найти простые множители числа
  8. Бинарный поиск
  9. Сортировка выбором
  10. Сортировка пузырьком O(n*n)
  11. Сортировка quick O(log2n*n) (максимально эффективная)
  12. Факториал (числа умноженные до текущего числа)
  13. Фибоначи
  14. Логарифм log
  15. Задачка

Ссылки

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)