Небольшое веселое соревнование между алгоритмами разных задач.
Уважаемый читатель,
Это будет забавный блог о том, как работают лучшие алгоритмы и как реализовать их в псевдокоде, а также некоторые подробности о них.
So 1,2,3 go….
Правила и этапы конкурса: -
- Будет 3 тура
- Каждый алгоритм будет оцениваться по временной и пространственной сложности.
- Каждому читателю будет выдан жетон сертификации для участия.
- Первый раунд будет алгоритмом сортировки.
- Второй этап - алгоритм обхода дерева.
- Третий раунд будет бонусным, без победителей и проигравших, только игроки с моими любимыми функциями активации.
Первый раунд:-
Нам нужны методы сортировки в основном каждый день для очистки данных и для чтения данных, а иногда для обработки и сортировки огромных беспорядочных наборов данных.
Наши номинанты - это быстрая сортировка, нечет-четность и коктейль, я знаю, что они не распространены.
Быстрая сортировка: -
Quicksort - это эффективный алгоритм сортировки. Этот алгоритм, разработанный британским ученым-компьютерщиком Тони Хоаром в 1959 году и опубликованный в 1961 году, до сих пор остается широко используемым алгоритмом сортировки. При правильной реализации он может быть примерно в два или три раза быстрее, чем его основные конкуренты, сортировка слиянием и сортировка в кучах.
нечетно-четная сортировка: -
В вычислениях сортировка по четным и нечетным данным или сортировка с перестановкой нечетных и четных является относительно простым алгоритмом сортировки, первоначально разработанным для использования на параллельных процессорах с локальными соединениями. Это сортировка сравнения, связанная с пузырьковой сортировкой, с которой она имеет много общих характеристик.
Сорт коктейля: -
Сортировка коктейльных шейкеров, также известная как двунаправленная пузырьковая сортировка, коктейльная сортировка, шейкерная сортировка, волновая сортировка, случайная сортировка или челночная сортировка, является расширением пузырьковой сортировки. Алгоритм расширяет пузырьковую сортировку, работая в двух направлениях.
код в Python по адресу: -
Псевдокоды
function quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p - 1)
quicksort(A, p + 1, hi)
function partition(A, lo, hi) is
pivot := A[hi]
i := lo
for j := lo to hi do
if A[j] < pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
function A = cocktailShakerSort(A)
#`beginIdx` and `endIdx` marks the first and last index to check
beginIdx = 1;
endIdx = length(A) - 1;
while beginIdx <= endIdx
newBeginIdx = endIdx;
newEndIdx = beginIdx;
for ii = beginIdx:endIdx
if A(ii) > A(ii + 1)
[A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
newEndIdx = ii;
end
end
#decreases `endIdx` because the elements after `newEndIdx` are in correct order
endIdx = newEndIdx - 1;
for ii = endIdx:-1:beginIdx
if A(ii) > A(ii + 1)
[A(ii+1), A(ii)] = deal(A(ii), A(ii+1));
newBeginIdx = ii;
end
end
#increases `beginIdx` because the elements before `newBeginIdx` are in correct order
beginIdx = newBeginIdx + 1;
end
end
function oddEvenSort(list) {
function swap(list, i, j) {
var temp = list[i];
list[i] = list[j];
list[j] = temp;
}
var sorted = false;
while (!sorted) {
sorted = true;
for (var i = 1; i < list.length - 1; i += 2) {
if (list[i] > list[i + 1]) {
swap(list, i, i + 1);
sorted = false;
}
}
for (var i = 0; i < list.length - 1; i += 2) {
if (list[i] > list[i + 1]) {
swap(list, i, i + 1);
sorted = false;
}
}
}
}
Quicksort имеет временную сложность O (log n) и пространственную сложность O (n).
Сортировка по нечетному и четному имеет временную сложность O (n²) и пространственную сложность O (1).
Сортировка коктейлей имеет сложность пространства O (n²) и O (1).
Итак, время для оценки: -
В категории временной сложности для сортировки победителем является Quicksort.
В категории космической сложности по сортировке победителем признан коктейльный сорт.
Второй раунд:-
Обход дерева - очень важная часть любого двоичного дерева, он помогает нам обходить или сортировать двоичное дерево. Обход - это процесс посещения всех узлов дерева и может также распечатать их значения. Поскольку все узлы соединены ребрами, мы всегда начинаем с корневого узла. То есть мы не можем получить произвольный доступ к узлу в дереве.
Кандидатами являются Inorder, Preorder и postorder.
Чтобы:-
В этом методе обхода сначала посещается левое поддерево, затем корень, а затем правое поддерево. Мы всегда должны помнить, что каждый узел может представлять собой поддерево.
Если пройти по бинарному дереву по порядку, на выходе будут получены отсортированные значения ключей в возрастающем порядке.
Мы начинаем с A и после обхода по порядку переходим к его левому поддереву B. B также просматривается по порядку. Процесс продолжается до тех пор, пока не будут посещены все узлы. Результатом обхода этого дерева будет -
D → B → E → A → F → C → G
Предзаказ:-
в этом методе обхода сначала посещается корневой узел, затем левое поддерево и, наконец, правое поддерево.
Мы начинаем с A и после обхода предварительного заказа сначала посещаем сам A, а затем переходим к его левому поддереву B. B также проходит предварительный заказ. Процесс продолжается до тех пор, пока не будут посещены все узлы. Результат предварительного просмотра этого дерева будет -
A → B → D → E → C → F → G
Пост-заказ: -
Пост-заказ обход
В этом методе обхода корневой узел посещается последним, отсюда и название. Сначала мы проходим левое поддерево, затем правое поддерево и, наконец, корневой узел.
Мы начинаем с A и после обхода пост-заказа сначала посещаем левое поддерево B. B также проходит пост-заказ. Процесс продолжается до тех пор, пока не будут посещены все узлы. Результатом обхода этого дерева после заказа будет -
D → E → B → F → G → C → A
Порядок уровней: -
Обход дерева в порядке уровней - это обход дерева в ширину.
Порядок обхода приведенного выше дерева в порядке уровней 1 2 3 4 5
Algorithm Inorder(tree)
1. Traverse the left subtree, i.e., call Inorder(left-subtree)
2. Visit the root.
3. Traverse the right subtree, i.e., call Inorder(right-subtree)
Algorithm Preorder(tree)
1. Visit the root.
2. Traverse the left subtree, i.e., call Preorder(left-subtree)
3. Traverse the right subtree, i.e., call Preorder(right-subtree)
Algorithm Postorder(tree)
1. Traverse the left subtree, i.e., call Postorder(left-subtree)
2. Traverse the right subtree, i.e., call Postorder(right-subtree)
3. Visit the root.
Algorithm Levelorder(tree)
for d = 1 to height(tree)
printGivenLevel(tree, d);
function printGivenLevel(tree, level)
if tree is NULL then return;
if level is 1, then
print(tree->data);
else if level greater than 1, then
printGivenLevel(tree->left, level-1);
printGivenLevel(tree->right, level-1);
И теперь победителем является обход Inorder Tree, потому что он самый быстрый из всех.
Третий раунд: -
Функции активации являются наиболее неотъемлемой и важной частью любой нейронной сети, от простого яблока или банана до сложной классификации и прогнозирования климата до небольшого устройства, которое вы носите с собой и читаете и разговариваете с ним.
Наши номинанты: ReLU, Sigmoid, Softmax и TanH.
ReLU: -
Выпрямленная линейная функция активации или сокращенно ReLU - это кусочно-линейная функция, которая выводит входной сигнал напрямую, если он положительный, в противном случае он выдает ноль. Она стала функцией активации по умолчанию для многих типов нейронных сетей, потому что модель, в которой она используется, легче обучать и часто обеспечивает лучшую производительность.
Сигмовидная: -
Сигмовидная функция - это математическая функция, имеющая характеристическую S-образную кривую или сигмовидную кривую. Типичным примером сигмовидной функции является логистическая функция, показанная на первом рисунке и определяемая формулой.
Софтмакс: -
ТанХ: -
В математике гиперболические функции являются аналогами обычных тригонометрических функций, определенных для гиперболы, а не для окружности: точно так же, как точки образуют окружность с единичным радиусом, точки образуют правую половину равносторонней гиперболы.
функция: -
SinH (х) = 1/2 * (е ^ х-е ^ -х)
CosH (x) = 1/2 * (e ^ x + e ^ -x)
TanH (x) = SinH (x) / CosH (x)
Код Python по адресу: -
Но мне очень жаль, что я не написал код для TanH на python, поэтому я добавлю код только в этот блог.
Псевдокоды
function sigmoid x return 1/1+e^x function softmax x y = [] for i in range n(x) eq = x[i]/sum(x) insert eq into y return y sub-function sum x tmp = 0 for i in x tmp+=i return tmp function ReLU x if x > 0: return x else: return 0 function TanH x y = (1/2*(e^x-e^-x))/(1/2*(e^x+e^-x))
Код функции TanH в Python: -
import numpy as np
def f(x):
y = (1/2*(np.exp(x)-np.exp(-x))/(1/2*(np.exp(x)+np.exp(-x))
return y
Спасибо за чтение:-
Будьте в безопасности во время пандемии Covid-19. Еще раз спасибо или читайте, следите за обновлениями и продолжайте читать.
Удачного ведения блога.
Хотите получать от меня больше блогов и информационных бюллетеней подписывайтесь
