So why do you need to know Algorithms and Data Structures in Front-end, anyway
Adam Leos
Adam Leos
Adam Leos
Adam Leos
Что вы видите, это не то, что исполняется ©
Что вы видите, это не то, что исполняется ©
Нет плохого кода, а есть плохие компиляторы ©
Сложность алгоритма
Сложность алгоритма
Big O notation, O
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n)
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n)
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
c and n0 are constants, f(n) and g(n) are functions over non-negative integers
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
c and n0 are constants, f(n) and g(n) are functions over non-negative integers
Сложность алгоритма
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
c and n0 are constants, f(n) and g(n) are functions over non-negative integers
Algorithm Complexity
Big O notation, O
Omega notation, Ω
Theta Notation, θ
asymptotic notations, asymptotic complexity
O(n) Ο(log n) O(n * logn)
logarithmic polynomial
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
c and n0 are constants, f(n) and g(n) are functions over non-negative integers
Сложность алгоритма
Сложность алгоритма
Как будет расти расход ресурсов* с увеличением размера входных данных.
Сложность алгоритма
Как будет расти расход ресурсов* с увеличением размера входных данных.
* время и память
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}��sumNumbersInArray([1, 2, 3, 4, 5]);
Сложность алгоритма
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}��sumNumbersInArray([1, 2, 3, 4, 5, 6, 7, 8, 9, 10]);
Сложность алгоритма
Как будет расти расход ресурсов* с увеличением размера входных данных.
* время и память
Big O notation, O
Big O notation, O
Big O notation, O
Функция, которая описывает рост сложности алгоритма.
Big O notation, O
function sumNumbersInArray(array) {� let sum = 0;�� array.forEach(number => sum += number);�� return sum;�}�
Размер входных данных, ед.
Размер входных данных, ед.
1
Размер входных данных, ед.
1
100
Размер входных данных, ед.
1
100
1000
Размер входных данных, ед.
1
100
1000
10000
Размер входных данных, ед.
1
100
1000
10000
Размер входных данных, ед.
1
100
1000
10000
Количество операций
Размер входных данных, ед.
1
100
1000
10000
Количество операций
1
100
1000
10000
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
Количество операций
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(n)
Количество операций
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(n) - линейная
Количество операций
Big O
function simpleCalculate() {� const a = 1 + 2;� const b = 3 + 4;�� console.log('calculating...');�� return b - a;�}��simpleCalculate();�
Big O
function simpleCalculate() {� const a = 1 + 2;� const b = 3 + 4;�� console.log('calculating...');�� return b - a;�}��simpleCalculate();�
O(1)
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(1)
Количество операций
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(1) - константная (постоянная)
Количество операций
Big O
function simpleCalculate(number) {� const a = 1 + 2;� const b = 3 + 4;�� console.log('calculating...');�� return b - a + number;�}��simpleCalculate(8);
Big O
function simpleCalculate(number) {� const a = 1 + 2;� const b = 3 + 4;�� console.log('calculating...');�� return b - a + number;�}��simpleCalculate(8);
O(1)
Big O
function simpleCalculate(array) {� const a = 1 + 2;� const b = 3 + 4;� let additionalNumber = 0;�� array.forEach(num => additionalNumber += num);�� return b - a + additionalNumber;�}��simpleCalculate([1, 2, 5, 10, 1223]);
Big O
function simpleCalculate(array) {� const a = 1 + 2;� const b = 3 + 4;� let additionalNumber = 0;�� array.forEach(num => additionalNumber += num);�� return b - a + additionalNumber;�}��simpleCalculate([1, 2, 5, 10, 1223]);
O(n)
Big O
function simpleCalculate(array) {� const a = 1 + 2;� const b = 3 + 4;� const additionalNumber = array.length;�� return b - a + additionalNumber;�}��simpleCalculate([1, 2, 5, 10, 1223]);
Big O
function simpleCalculate(array) {� const a = 1 + 2;� const b = 3 + 4;� const additionalNumber = array.length;�� return b - a + additionalNumber;�}��simpleCalculate([1, 2, 5, 10, 1223]);
O(1)
Big O
function notSoSimpleCalculate(array) {� for (let i = 0; i < array.length; i++) {� for (let j = 0; j < array.length; j++) {� array[i] = array[i] + array[j];� }� }�� return array;�}��notSoSimpleCalculate([1, 2, 3]);
Big O
function notSoSimpleCalculate(array) {� for (let i = 0; i < array.length; i++) {� for (let j = 0; j < array.length; j++) {� array[i] = array[i] + array[j];� }� }�� return array;�}��notSoSimpleCalculate([1, 2, 3]);
O(n^2)
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(n^2) - квадратичная
Количество операций
Big O
function notSoSimpleCalculate(array) {� array.forEach(num => console.log(num));�� for (let i = 0; i < array.length; i++) {� for (let j = 0; j < array.length; j++) {� array[i] = array[i] + array[j];� }� }�� return array;�}
Big O
function notSoSimpleCalculate(array) {� array.forEach(num => console.log(num));�� for (let i = 0; i < array.length; i++) {� for (let j = 0; j < array.length; j++) {� array[i] = array[i] + array[j];� }� }�� return array;�}
O(n^2)
Big O
function mightBeSimpleCalculate(array) {� let total = 0;�� array.forEach(num => {� const additional = array.indexOf(num) > 5 ? 5 : 1;
� total = total + num + additional;� });�� return array;�}
Big O
function mightBeSimpleCalculate(array) {� let total = 0;�� array.forEach(num => {� const additional = array.indexOf(num) > 5 ? 5 : 1;
� total = total + num + additional;� });�� return array;�}
O(n^2)
Big O
function mightBeSimpleCalculate(array) {� let total = 0;�� array.forEach(num => {� const additional = array.indexOf(num) > 5 ? 5 : 1;
� total = total + num + additional;� });�� return array;�}
O(n^2)
Big O
function mightBeSimpleCalculate(array) {� let total = 0;�� array.forEach((num, index) => {� const additional = index > 5 ? 5 : 1;�� total = total + num + additional;� });�� return array;�}
O(n)
Пример роста в цифрах
Пример роста в цифрах
Входные данные - 10000 элементов
Пример роста в цифрах
O(1) - 1
Входные данные - 10000 элементов
Пример роста в цифрах
O(1) - 1
O(n) - 10000
Входные данные - 10000 элементов
Пример роста в цифрах
O(1) - 1
O(n) - 10000
O(n^2) - 100000000 (сто миллионов)
Входные данные - 10000 элементов
Пример роста в цифрах
O(1) - 1
O(n) - 10000
O(n^2) - 100000000 (сто миллионов)
O(n^3) - 1000000000000 (один триллион)
Входные данные - 10000 элементов
Пример роста в цифрах
O(1) - 1
O(n) - 10000
O(n^2) - 100000000 (сто миллионов)
O(n^3) - 1000000000000 (один триллион)
O(n!) очень много 100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000……
Входные данные - 10000 элементов
Структуры данных
Структуры данных
Определенный способ организации данных для максимально эффективного использования
Структуры данных
Структуры данных
Массивы
const arr = [1, 2, 3];
Массивы
const arr = [1, 2, 3];
arr[1]; // 2
Массивы
const arr = [1, 2, 3];
arr[1]; // 2
O(1)
Массивы
const arr = [1, 2, 3];
arr[1]; // 2
arr[2]; // 3
O(1)
O(1)
Массивы
const arr = [1, 2, 3];
arr[1]; // 2
arr[2]; // 3
arr[9]; // undefined
O(1)
O(1)
O(1)
Массивы
const arr = [1, 2, 3];
arr[1]; // 2
arr[2]; // 3
arr[9]; // undefined
arr[0] = 4; // [4, 2, 3]
O(1)
O(1)
O(1)
O(1)
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
O(1)
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
arr.shift(); // [2, 3]
O(1)
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
arr.shift(); // [2, 3]
O(1)
O(n)
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
arr.shift(); // [2, 3]
arr.unshift(4); // [4, 2, 3]
O(1)
O(n)
O(1)*
Массивы
const arr = [1, 2, 3];
arr.push(4); // [1, 2, 3, 4]
arr.pop(); // [1, 2, 3]
arr.shift(); // [2, 3]
arr.unshift(4); // [4, 2, 3]
O(1)
O(n)
O(n)
O(1)*
Массивы
O(n)
Массивы
.map()
.slice()
.every()
.filter()
.indexOf()
.reduce()
.reverse()
.find()
.includes()
.toString()
O(n)
Структуры данных
Объекты
const obj = {� id: 1,� name: 'Adam',�};
Объекты
const obj = {� id: 1,� name: 'Adam',�};
obj.id // 1
Объекты
const obj = {� id: 1,� name: 'Adam',�};
obj.id // 1
O(1)
Объекты
const obj = {� id: 1,� name: 'Adam',�};
obj.id // 1
obj['name'] // 1
O(1)
O(1)
Объекты
const obj = {� id: 1,� name: 'Adam',�};
obj.surname = 'Leos';
obj['name'] = [];
O(1)
O(1)
Объекты
const obj = {� id: 1,� name: 'Adam',�};
Object.keys(obj) // ['id', 'name']
Object.values(obj) // [1, 'Adam']
Объекты
const obj = {� id: 1,� name: 'Adam',�};
Object.keys(obj) // ['id', 'name']
Object.values(obj) // [1, 'Adam']
O(n)
O(n)
Объекты
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
function countSymbols(string) {� const dict = {};�� for (let i = 0; i < string.length; i++) {� const iterableSymbol = string[i];� � if (dict[iterableSymbol] === undefined) dict[iterableSymbol] = 0;�� dict[iterableSymbol]++;� }�� return dict;�}
Посчитать символы в строке
Объекты
countSymbols('adam') // Object { a: 2, d: 1, m: 1 }
countSymbols('mississippi') // Object { m: 1, i: 4, s: 4, p: 2 }
Посчитать символы в строке
Полезный мапинг в
реальном мире
const shows = [� {� id: 1,� name: 'Rick and Morty',� categories: [
'Comedy',
'Animated',
'Science',
],
data: 1001010101001011,� },� {/.../},
{/.../},
{/.../},
{/.../},�];
const bannedShows = [� {
id: 1,
categories: [
'Comedy',
'Animated',
'Science',
],
},� {/.../},
{/.../},
{/.../},�];
const shows = [� {� id: 1,� name: 'Rick and Morty',� categories: [
'Comedy',
'Animated',
'Science',
],
data: 1001010101001011,� },� {/.../},
{/.../},
{/.../},
{/.../},�];
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function ineffectiveBanning(shows) {� shows.forEach(show => {� const { id: showID } = show;�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;�� if (showID === bannedShowID) {
show.isBanned = true;
};� });� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
function effectiveBanning(shows) {� const bannedShowsIDMap = {};�� bannedShows.forEach(bannedShow => {� const { id: bannedShowID } = bannedShow;� bannedShowsIDMap[bannedShowID] = true;� };�� shows.forEach(show => {� const { id: showID } = show;�� if (bannedShowsIDMap[showID]) show.isBanned = true;� });�};
x100
Память в реальном мире
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels� .filter(filterEmptyTimelines)� .map(addIdentificator)� .map(modifyImages)
.map(removeParams)� .map(setSession)�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
function enchanceApiResponse(apiResponse) {� const channels = apiResponse.channels.reduce((acc, channel) => {� if (hasEmptyTimelines(channel.timelines)) {� return acc;� }�� const enchancedChannel =
setChannelURL(reduceImagesObject(addIDToChannel(channel)));�� acc.push(enchancedChannel);�� return acc;� }, []);�� // more code�}
10-30%
Структуры данных
Граф
Граф
Вершина (узел)
Граф
Вершина (узел)
Ребро
Граф
Вершина (узел)
Ребро
1
13
9
54
11
6
70
Граф
1
13
9
54
11
6
70
Граф
1
13
9
54
11
6
70
Value (data) = 6
Граф
1
13
9
54
11
6
70
Value (data) = 6
Connections = [13, 70]
node = {� value: 6,� connections: [13, 70],�}
node = {� value: 6,� connections: [13, 70],�}
class Node {��}
node = {� value: 6,� connections: [13, 70],�}
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�}
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
const six = new Node(6);
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
const six = new Node(6);
six.value; // 6
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
const six = new Node(6);
six.value; // 6
const thirteen = new Node(13);�const seventy = new Node(70);�
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
const six = new Node(6);
six.value; // 6
�const thirteen = new Node(13);�const seventy = new Node(70);��six.addConnection(thirteen);�six.addConnection(seventy);
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
node = {� value: 6,� connections: [13, 70],�}
const six = new Node(6);
six.value; // 6
�const thirteen = new Node(13);�const seventy = new Node(70);��six.addConnection(thirteen);�six.addConnection(seventy);
six.connections;
// [{ value: 13, connections: [] }, { value: 70, connections: [] }];
class Graph {� �}
class Graph {� constructor() {� this.nodes = [];� } �}
class Graph {� constructor() {� this.nodes = [];� }�� addNode(node) {� this.nodes.push(node);� } �}
class Graph {� constructor() {� this.nodes = [];� }�� addNode(node) {� this.nodes.push(node);� }� � addEdge(node1, node2) {� node1.addConnection(node2);� node2.addConnection(node1);� }; �}
Граф
1
13
9
54
11
6
70
class Graph {� constructor() {� this.nodes = {};� }�� addNode(node) {� this.nodes.push(node);� }� � addEdge(node1, node2) {� node1.addConnection(node2);� node2.addConnection(node1);� }; �}
const ourGraph = new Graph();��const one = new Node(1);�const six = new Node(6);�const nine = new Node(9);�const eleven = new Node(11);�const thirteen = new Node(13);�const fiftyFour = new Node(54);�const seventy = new Node(70);
class Graph {� constructor() {� this.nodes = {};� }�� addNode(node) {� this.nodes.push(node);� }� � addEdge(node1, node2) {� node1.addConnection(node2);� node2.addConnection(node1);� }; �}
ourGraph.addNode(one);�ourGraph.addNode(six);�ourGraph.addNode(nine);�ourGraph.addNode(eleven);�ourGraph.addNode(thirteen);�ourGraph.addNode(fiftyFour);�ourGraph.addNode(seventy);��ourGraph.addEdge(one, thirteen);�ourGraph.addEdge(nine, thirteen);�ourGraph.addEdge(nine, fiftyFour);�ourGraph.addEdge(thirteen, eleven);�ourGraph.addEdge(thirteen, six);�ourGraph.addEdge(six, seventy);
Граф Гугл-карт
Kharkiv - [Lviv];
Lviv - [Kharkiv, Odessa];
Odessa - [Lviv];
Граф Гугл-карт
Kharkiv - [Lviv];
Lviv - [Kharkiv, Odessa];
Odessa - [Lviv];
Seattle
San Francisco
Las Vegas
Salt Lake City
San Francisco
Граф Гугл-карт
Kharkiv - [Lviv];
Lviv - [Kharkiv, Odessa];
Odessa - [Lviv];
const googleRoute = new Graph();��
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');�
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');�
const seattleData = {� name: 'Seattle',� coordinates: [� 47.7471188,� -125.6412592,� ],� state: 'WA',� country: 'USA',� weather: 'Sunny',� /.../�};
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');��googleRoute.addNode(seattle);�googleRoute.addNode(sanFrancisco);�googleRoute.addNode(lasVegas);�googleRoute.addNode(saltLakeCity);�
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');��googleRoute.addNode(seattle);�googleRoute.addNode(sanFrancisco);�googleRoute.addNode(lasVegas);�googleRoute.addNode(saltLakeCity);��googleRoute.addEdge(seattle, sanFrancisco);�googleRoute.addEdge(sanFrancisco, lasVegas);�googleRoute.addEdge(lasVegas, saltLakeCity);�googleRoute.addEdge(saltLakeCity, sanFrancisco);
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');��googleRoute.addNode(seattle);�googleRoute.addNode(sanFrancisco);�googleRoute.addNode(lasVegas);�googleRoute.addNode(saltLakeCity);��googleRoute.addEdge(seattle, sanFrancisco);�googleRoute.addEdge(sanFrancisco, lasVegas);�googleRoute.addEdge(lasVegas, saltLakeCity);�googleRoute.addEdge(saltLakeCity, sanFrancisco);
sanFrancisco.connections = [
seattle,
lasVegas,
saltLakeCity,
];
const googleRoute = new Graph();��const seattle = new Node('Seattle');�const sanFrancisco = new Node('San Francisco');�const lasVegas = new Node('Las Vegas');�const saltLakeCity = new Node('Salt Lake City');��googleRoute.addNode(seattle);�googleRoute.addNode(sanFrancisco);�googleRoute.addNode(lasVegas);�googleRoute.addNode(saltLakeCity);��googleRoute.addEdge(seattle, sanFrancisco);�googleRoute.addEdge(sanFrancisco, lasVegas);�googleRoute.addEdge(lasVegas, saltLakeCity);�googleRoute.addEdge(saltLakeCity, sanFrancisco);
sanFrancisco.connections = [
seattle,
lasVegas,
saltLakeCity,
];
seattle.connections = [
sanFrancisco
];
Логистика
Граф
1
13
9
54
11
6
70
Граф - ориентированный
1
13
9
54
11
6
70
Граф - взешенный
1
13
9
54
11
6
70
4
2
7
20
8
1
Где еще используются графы
Структуры данных
Деревья
1
13
9
54
11
6
70
Деревья
=
Связный ацикличный граф
1
13
9
54
11
6
70
Деревья
=
Связный ацикличный граф
1
13
9
54
11
6
70
Деревья
=
Связный ацикличный граф
1
13
9
54
11
6
70
DOM дерево
const settings = {� �};�
const settings = {� options: [� � ],�};�
const settings = {� options: [� {� � },� {� � },� {� � },� // ... � ],�};�
const settings = {� options: [� {� name: 'video',� options: [...],� },� {� name: 'sound',� options: [...],� },� {� name: 'security',� options: [...],� },� // ... � ],�};�
const settings = {� options: [� {� name: 'video',� options: [...],� },� {� name: 'sound',� options: [...],� },� {� name: 'security',� options: [...],� },� // ... � ],�};�
[
{
name: 'subtitles',
options: [...],
},
{
name: 'brightness',
options: [...],
},
// ...�];�
Алгоритмы
Алгоритмы
function find(number, array) {� array.forEach((iterableNumber, index) => {� if (iterableNumber === number) {
console.log(`Found at index ${index}`);
}� });�}
function find(number, array) {� array.forEach((iterableNumber, index) => {� if (iterableNumber === number) {
console.log(`Found at index ${index}`);
}� });�}
O(n)
Поиск. Бинарный vs Последовательный
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
function binarySearch(number, array) {� let startIndex = 0;� let endIndex = array.length - 1;�� while (startIndex <= endIndex) {� const middleIndex = Math.floor((startIndex + endIndex) / 2);� const middleValue = array[middleIndex];�� if (middleValue === number) {� console.log(`Found at index ${middleIndex}`);� } else if (middleValue < number) {� startIndex = middleIndex + 1;� } else {� endIndex = middleIndex - 1;� }� }�}
O(logn)
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(logn) - логарифмическая
Количество операций
Размер входных данных, ед.
1
100
1000
10000
1
100
1000
10000
O(logn) - логарифмическая
2el => 1
4el => 2
8el => 3
1000el => ~10
10000el => ~13
100000el => ~16
Количество операций
Бинарное
Дерево
1
13
9
54
11
6
70
Бинарное
Дерево
1
3
9
54
11
6
70
Бинарное
Дерево
1
3
5
54
11
6
70
Бинарное
Дерево
1
3
5
54
71
6
70
Поиск. Бинарное дерево
class Node {� constructor(value) {� this.value = value;� this.connections = [];� }�� addConnection(node) {� this.connections.push(node);� }�}
class Node {� constructor(value) {� this.value = value;� this.left = null;� this.right = null;� }�}
class Tree {� constructor() {� this.root = null;� } �}
class Tree {� constructor() {� this.root = null� }
insert(data) {� const newNode = new Node(data);� � if (this.root === null) {
this.root = newNode;
} else {
this.insertNode(this.root, newNode);
}� } �}
Бинарное дерево
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
insertNode(parentNode = this.head, newNode) {� if (newNode.data < parentNode.data) {� if (parentNode.left === null) parentNode.left = newNode;� else {
this.insertNode(parentNode.left, newNode);
}� } else {� if (parentNode.right === null) parentNode.right = newNode;� else {
this.insertNode(parentNode.right, newNode);
}
}�}�
Алгоритмы
Сортировка Пузырьком (bubble sort)
Сортировка Пузырьком (bubble sort)
O(n^2)
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
function bubble(arr) {� const length = arr.length;�� for (let i = 0; i < length; i++) {� for (let j = 0; j < length - i - 1; j++) {� const current = arr[j];� const next = arr[j + 1];�� if (current > next) {� arr[j] = next;� arr[j + 1] = current;� }� }� }�� return arr;�}
Сортировка слиянием
(Merge sort)
Сортировка слиянием
(Merge sort)
O(n * logn)
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function mergeSort(unsortedArray) {� if (unsortedArray.length <= 1) {� return unsortedArray;� }�� const middle = Math.floor(unsortedArray.length / 2);� const left = unsortedArray.slice(0, middle);� const right = unsortedArray.slice(middle);�� return merge(� mergeSort(left), mergeSort(right)� );�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
function merge(left, right) {� const resultArray = [];� let leftIndex = 0;� let rightIndex = 0;�� while (leftIndex < left.length && rightIndex < right.length) {� if (left[leftIndex] < right[rightIndex]) {� resultArray.push(left[leftIndex]);� leftIndex++;� } else {� resultArray.push(right[rightIndex]);� rightIndex++;� }� }�� return resultArray� .concat(left.slice(leftIndex))� .concat(right.slice(rightIndex));�}
Память vs. Время
Bogosort
(самая неэффективная сортировка)
Bogosort
(самая неэффективная сортировка)
O(n * n!)
Уже хорошо работает
Array.sort()
Уже хорошо работает
Array.sort()
Разные имплементации в разных браузерах. (и в разных версиях).
Уже хорошо работает
Array.sort()
Разные имплементации в разных браузерах. (и в разных версиях).
В целом, базируется на сортировках слиянием и быстрой сортировке (в зависимости от типа данных в массиве).
Уже хорошо работает
Array.sort()
Разные имплементации в разных браузерах. (и в разных версиях).
В целом, базируется на сортировках слиянием и быстрой сортировке (в зависимости от типа данных в массиве).
+ на небольших массивах (до 10 элементов) используется сортировка вставками.
Заключение
Заключение
Заключение
Заключение
Материалы
Q&A
Слайды
Контакты