Нотация "О"
*. В чем идея "Big O Notation"?
*. Существует 10–20 различных способов решения проблемы. Используя нотацию Big O, мы можем найти лучший подход к решению проблемы.
ex: напишите функцию для вычисления суммы всех чисел от 1 до n.
sol: есть два основных подхода к этому.
Приложение1: функция addUpTo (n) {
let sum = 0;
for (let i = 0; i ‹n; i ++) {
sum + = i ;
}
возвратная сумма
}
Приложение2: функция addUpTo (n) {
return (n * (n - 1) / 2);
}
В нотации Big O Notation мы подсчитываем «количество простых операций», которые компьютер должен выполнить.
В подходе 2 у нас есть 3 операции (*, -, /), поэтому для любого значения «n» эти 3 операции останутся постоянными.
В подходе 1 мы имеем следующее:
‹I› сумма = 0; один раз
‹Ii› i = 0 тоже будет один раз,
‹Iii› i ‹n && i ++ операция будет выполнена n раз, т.е. 3n
‹Iv› + = (сложение n присваиваний) n раз, т.е. 2n
результат: ›i (const) + ii (const) + 3 * n + 2 * n =› (5n + 2).
************** Углубленное введение в нотацию Big O *************
Он говорит нам, «как время выполнения алгоритма растет по мере увеличения« размера входных данных ».
По сути, это взаимосвязь между «размером ввода» и «временем относительно» этого ввода.
По сути, это связь между тем, как изменяется размер ввода и время, необходимое для выполнения набора операций над вводом.
Математическое представление: O (f (n)).
Согласно вышеприведенному представлению, «n - размер ввода», а «f (n) - время, необходимое для выполнения алгоритма для этого размера ввода».
Существует три основных варианта O (f (n)):
*. f (n) может быть линейным, т.е. f (n) = n.
*. f (n) может быть квадратичным, т.е. f (n) = n * n.
*. f (n) может быть постоянным, т.е. f (n) = 1.
Ниже приведены несколько примеров для представления сценариев:
*. Линейный регистр:
function countUpAndDown () {
// при изменении значения n изменяются и выполняемые простые операции.
for (let i = 1; i ‹= n; i ++) {
console.log (я)
} // n почему? - цикл for продолжается до n раз
for (пусть j = n; j ‹= 1; j -) {
console.log (j)
} // n почему? - цикл for продолжается до n раз в обратном порядке
/*
следовательно, n + n = 2n, но мы игнорируем константу, поскольку для бесконечности
константа не имеет значения.
*/
}
ПРАВИЛА ПАЛЬЦА:
- - - - - -
Правило 1. Константа не имеет значения, если взять бесконечность.
O(2n) = O(n)
O(500) = O(1)
O(13n*n) = O(n*n)
O(n+10) = O(n)
O(1000n + 50) = O(n)
O(n*n + 5n + 8) => n*n + 5n => n(n+5) = O(n*n).
O(n*n + n*n*n) => (n*n(n + 1)) = O(n*n*n)
*. Когда мы увеличиваем график между f (n) («временная сложность») и n («размер ввода») до бесконечности, постоянное значение становится незначительным и игнорирующим.
*. Арифметические операции, присвоение переменных и доступ к элементам в массиве / объекте постоянны.
ПРОСТРАНСТВО-СЛОЖНОСТЬ
Сколько дополнительной памяти нам нужно выделить, чтобы запустить код в нашем алгоритме?
Сложность вспомогательного пространства:
Это относится к пространству, требуемому алгоритмом, не включая пространство, занимаемое входными данными.
ПРАВИЛА ПАЛЬЦА:
1. Большинство примитивных типов данных - это постоянное пространство.
2. Строке требуется пространство O (n), где n - длина строки.
3. Типы ссылок обычно O (n), где n - длина строки. длина массива n в случае объекта - количество ключей.
Пример: массив 1 имеет длину 4 n Массив 2 имеет длину 2, в результате чего массив 1 будет занимать пространство, вдвое превышающее массив 2.
Пример 1: Определите сложность пространства?
функция sum (arr) {
let total = 0;
for (let i = 0; i ‹arr.length; i ++) {
total + = arr [i]; // примитивный тип данных
}
return total;
}
sum ([1,2,3,4])
Наблюдение: независимо от длины массива, пространство будет занято только сразу, следовательно, сложность пространства будет постоянной.
ex2: найти космическую сложность?
функция double (arr) {
let nwArr = [];
for (let i = 0; i ‹arr.length; i ++) {
nwArr.push (arr [i]);
}
return nwArr;
}
Наблюдение: размер массива будет увеличиваться в соответствии с размером входного массива, следовательно, O (N).
пример 3: функция onlyElementsAtEvenIndex () {
let array = [1,2,3,4,5,6],
nwArr = [ ];
for (let i = 0; i ‹array.length; i ++) {
if (arr [i]% 2 == 0) {
nwArr.push (arr [i ]);
}
}
return nwArr;
}
ЛОГАРИФМЫ
По сути, это обратное экспоненте, так же как умножение и деление - пара.
Логарифмы и экспоненты являются парными.
*. Пример: log2 (8) = 3; // log2 (значение) = показатель степени → умножение 2 ‹exponent› на значение равно значению.
*. Что это означает: Это означает, что степень двойки равна 8, что, очевидно, будет равно 3.
*. Логарифмы всегда работают с основанием 2.
Примечание. Логарифм числа примерно определяет, сколько раз мы можем разделить это число на 2, прежде чем получим значение, меньшее или равное 1.
Ниже показано соотношение между временем O (N) и количеством элементов (N)
ПОИСК ОБЪЕКТОВ / МАССИВ ЧЕРЕЗ BIG O
let инструктор = {
‘firstName’: ‘Kelly’,
‘isInstructor’: true,
‘favNbrs’: [1,2,3,4]
};
# Ниже приведены действия с объектом, порядок которых не важен:
1. Вставка: O (1) // добавление нового свойства.
2 . Удаление: O (1) // удаление свойства.
3. Поиск: O (N)
4. Доступ: O (1) - console.log (инструктор ['isInstructor'])
# Большое количество объектных методов
1. Object.keys () - O (N)
2. Object.values () - O (N)
3. Object.entries () - O (N)
4. .hasOwnProperty () - O (1), поскольку это похоже на доступ к свойству.
# массивов
1. Доступ к значениям - O (1)
В случае доступа к конкретному значению мы знаем точное местоположение / индекс, в результате временная сложность остается O (1) независимо от длины массива.
2. Поиск - O (N)
В случае поиска мы не знаем точного индекса, в котором находится конкретное значение, в результате мы можем перейти к последнему значению индекса в массиве.
3. Вставка:
В массив мы выполняем вставку двумя способами: push и pop.
Push: мы добавляем значение в последний индекс, поэтому Большой O будет O (1).
Pop: мы удаляем непосредственно из последнего значения индекса, поэтому большой O будет O (1).
Сдвиг: мы удаляем значение из первого индекса, в результате индекс остального значения повторно сдвигается до последнего элемента массива, поэтому Большой O будет O (N).
Unshift: мы добавляем значение к первой позиции индекса массива, что приводит к повторной индексации массива, поэтому большой O будет O (N).
Concat: это в основном объединение 2 или более массивов или просто вставка элементов одного массива в другой, это зависит от итерации массива, в результате БОЛЬШОЙ O будет O ( N).
Slice / Splice: в этих методах итерационная часть входит в ролевую игру и пропорциональна длине массива, поэтому Big O будет O (N).
Сортировка: большая буква O будет равна O (N * logN).
forEach / map / filter / reduce: Big O будет O (N), потому что итерация равна длине массива.
Вкратце: в случае массива и объектов, когда мы знаем индекс или ключ объекта для доступа к значению, в этом случае это O (1), но когда нам нужно выполнить итерацию для поиска значения как в случае массива, так и в случае объекта Big O будет O (N).
Примечание. Объекты быстро справляются практически со всем, но нет порядка, а массивы отлично подходят, когда нам нужен порядок.
ВВЕДЕНИЕ В РЕШЕНИЕ ПРОБЛЕМ
*. Что такое алгоритм?
*. Это набор шагов для выполнения определенной задачи.
*. Разберитесь в проблеме
*. Изучите конкретные примеры
*. Разбейте
*. Решить и упростить
*. Повторный цикл и рефакторинг
- Понимание проблемы
A. Могу я переформулировать проблему своими словами?
B. Что входит в проблему?
C. Каков результат решения проблемы? D. Достаточно ли у меня информации для решения проблемы?
E. Как мне пометить важные фрагменты данных, которые являются частью проблемы?
Ex1: напишите функцию, которая принимает 2 числа и возвращает их сумму.
Подход:
A. Нам нужно реализовать дополнительные функции.
B. Тип входных данных: число / Вводимое количество: два числа
C. Тип возвращаемых данных - число
D. Что нужно сфокусировать по типу входных данных: Пусто, Тип данных, Недействительный, Смешанный правильный и неправильный.
Ex2: напишите функцию, которая принимает строку и возвращает количество каждого символа в строке.
Подход:
A. Необходимо найти символы в строке.
Б. Ниже приведены исходные данные, которые используются для решения проблемы. (Анализ)
*. «Мой номер телефона 182763» (Нужно ли учитывать пробелы или цифры?)
*. ‘Hello Li’ (нужно указать прописными буквами или нет)
*. Пустые / смешанные / недопустимые типы данных.
C. Разбейте его на части:
Разбейте все решение проблемы на шаги.
Какие шаги мы будем выполнять, чтобы выполнить нашу задачу .
*. Сначала нам нужно выполнить базовую функциональность / логику.
*. Во-вторых, мы должны попробовать уровень проверки / тип ввода.
# Есть несколько разных подходов / шаблонов для написания кода:
- Счетчик частоты
- Множественный указатель
- Скользящее окно
- Разделяй и властвуй
- Динамическое программирование
- Жадные алгоритмы
- Обратное отслеживание
В этой статье мы подробно рассмотрим все вышеперечисленные пункты один за другим с чертовски большим количеством примеров:
- Счетчик частоты // БЕСПЛАТНО
