Рубрика: Алгоритмы

Массивы «пузырьковая сортировка»

Автор записи Автор: bo52
Дата записи 05.01.2020

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)

Алгоритмы Массивы "cортировка"

Массивы «cортировка выбора»

Автор записи Автор: bo52
Дата записи 05.01.2020

O(k*n*n)=>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 selectionSort(arr){
 for (let i = 0; i < arr.length; i++) {
  let indexMin = i
  for (let j=i+1; j < arr.length; j++){
   if (arr[i] < arr[indexMin]){
 indexMin=j
}
}
let tmp = arr[i];
arr[i]=arr[indexMin]
arr[indexMin]=tmp
}
}
console.log(selectionSort(arr))
console.log(arr.length)//))O(k*n*n)
console.log('count = ', count)

Алгоритмы Массивы "поиск"

Массивы «Бинарный поиск»

Автор записи Автор: bo52
Дата записи 04.01.2020

O(log₂n)
для массива из 1000 элементов
O(log₂1000)

время сортировки массива более длительнее чем работа линейного поиска

требование
массив отсортирован по порядку

Процесс выполнения

смотрим по середине символ
— если символ идет раньше, которую мы открыли, то будем
рассматривать левую часть
— если символ идет позже, которую мы открыли, то будем
рассматривать правую часть
таким образом каждый раз мы отсеиваем ровно половину в массиве пока не найдем элемент

количество итераций — счетчик выполнения оператора for

const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;

function binarySearch(arr, item){
 let start = 0
 let end = arr.length;
 let middle;
 let found = false;
 let position = -1;
 while (found === false && start <= end){
  cnt+=1
  middle = Math.floor((start+end)/2);
  if (arr[middle] === item){
   found = true
   position = middle
   return position;
  }
  if (item < arr[middle]){
   end = middle-1
  } else {
   start = middle+1
  }
  return position;
}
console.log(binarySearch(arr,0))
console.log(cnt);

рекурсивный код более локаничный

cnt=0;
function recursiveBinarySearch(arr,item,start,end){
  let middle = Math.floor((start+end)/2);
  cnt+=1
  if (item == arr[middle]){
   return middle;
  }
  if (item < arr[middle]){
   return recursiveBinarySearch(arr,item,start,middle-1)
} else {
  return recursiveBinarySearch(arr,item,middle+1,end)
 }
}
console.log(recursiveBinarySearch(arr,12,0,arr.length))
console.log(cnt);

Алгоритмы Массивы "поиск"

Массивы «линейный поиск»

Автор записи Автор: bo52
Дата записи 03.01.2020

последовательно сравниваем с тем элементом, который ищем

массив из n элементов
O(n)
n — количество итераций в массиве

для массива из 1000 элементов
O(1000)

лучший случай
элемент находим в начале списка за одну операцию

худший случай
элемент находим в конце списка

сложность
нам необходимо пройтись по каждому элементу, который в этом списке находится

const arr=[1,4,5,8,51,2,7,5,5,2,11]
let cnt = 0;//количество итераций
function linearSearch(arr, item){
 for (let i =0; i< arr.length; i++){
  cnt+=1;
  if (arr[i] === item) {
   return i;
  }
 }
 return null;
}
console.log(linearSearch(arr, 11));
console.log('count = ', count);

Алгоритмы

О(n)

Автор записи Автор: bo52
Дата записи 02.01.2020

«О большое»

сложность алгоритма, или же его скорость алгоритмов описывается с помощью специальной аннотации

(n) в скобках

указывается количество операций, за которое этот алгоритм приходит к финальному результату

указывается всегда наихудшая ситуация

типы графиков

по скорости выполнения
от лучшего до наихудшего

t=1
t=log₂n
t=n
t=n*log₂n
t=n*n
t=n!

Например

Поиск элемента в массиве (линейный)

для массива из 1000 элементов
O(1000)

массив из n элементов
O(n)