Алгоритмы — это «способ ведения дел». Просто дискретный. Разделено на этапы. Пошаговый план достижения определенной цели. Это гарантирует получение одного и того же результата для одного входа. Полное руководство по решению проблемы. Это Алгоритм.
В основе программирования (или кодирования/разработки программного обеспечения или любого другого крутого слова, которое мы используем в наши дни) лежат алгоритмы (алго короче). Как мы знаем, действие без плана далеко не соответствует ожиданиям. В программировании алгоритм — это наше планирование.
В Интернете доступно множество веб-ссылок, в которых одни и те же вещи рассматриваются по-разному. Но ничто не сравнится с чтением книги 📚согласитесь 😁.
Очень рекомендуемая книга:
Введение в алгоритмы, 3-е издание (MIT Press)
Томас Х. Кормен,
Чарльз Э. Лейзерсон,
et al. | 31 июля 2009 г.
https://www.amazon.com/Data-Structures-Thomas-H-Cormen-Algorithms/
Блок-схемы:
Блок-схема — это тип диаграммы, которая представляет рабочий процесс или процесс. Блок-схему также можно определить как схематическое представление алгоритма, пошагового подхода к решению задачи. — википедия
Визуализация вашего решения часто помогает прикрыть крайние случаи и прояснить мысли. Блок-схемы — это действительно полезный способ представить дизайн алгоритма другим и себе.
Блок-схемы — это круто. Используйте draw.io.
Чтобы решить проблему — используйте алгоритм — для представления алгоритма — используйте блок-схемы.
Прохладный. останься со мной. впереди самое интересное:
Сложность:
После того, как у нас есть решение, проверено на каждом этапе. Мы должны рассмотреть возможность того, что какое-то другое решение может оказаться лучше. Теперь, как сравнить решения? "Правильный. Ты. Мой друг» (Мастер Йода): Сложность.
В индустрии программного обеспечения мы рассматриваем сложность как меру, позволяющую решить, выбирать ли алгоритм или нет. Сложность может иметь 2 фактора:
- ВРЕМЯ: ок. количество времени, которое занимает ваше решение
- ПРОСТРАНСТВО: ок. пространство, занятое вашим решением
Мы будем представлять сложность относительно «n», где n — длина входного набора.
Оповещение о правилах для большого пальца 🚨
👍 Время бесценно. Пространство можно купить
👍 Нотации Big Oh(O) — наши друзья
👍 Операторы выполнения и циклы съедают ваше время
👍 Рекурсия съедает ваше время
Обозначение большого O:
O(1): read(order of 1) — лучшее, что можно сделать. O(n): read(порядок en) означает, что сложность увеличивается пропорционально длине входного набора (т. е. n). Программы проводят большую часть своего времени в циклах. Так что смотрите.
Примеры (временная сложность) 🖥 ⏰
O(1): не относительно ‘n’
aka Постоянное время. Цели программирования 🤞.
sum = a+b // constant time O(1) anotherSum = (a+b) * 10000000000 // constant time O(1) somethingElse = functionCall() // depends of function def. duh!
O (n): постоянный коэффициент «n»
Порядок «н». Лучшее, чего вы можете достичь большую часть времени.
for(var i=0; i<n; i++) {} // loop runs n times
for(var i=0; i<100000; i++) { // loop runs 100000*n times
for (var i=0; j<n; j++) {}
}
O(log n): логарифмический (base2) множитель n.
В цикле значение i либо уменьшается на половину (потому что base2), либо увеличивается два раза от его значения на каждой итерации.
/*
* for n=256, loop runs 8 times
* for n=128, loop runs 7 times
* for n=016, loop runs 4 times
* looks like "log2 n" in picture
*/
for(var i=n; i>=0; i/=2) {} // i reduces by 1/2 in each iteration
for(var i=0; i<n; i*=2) {} // i increases by *2 in each iteration
Если «i» уменьшает на одну треть, на каждой итерации записывайте в журнал (base3):
/*
* for n=003, loop runs 1 times
* for n=009, loop runs 2 times
* for n=027, loop runs 3times
* looks like "log3 n" in picture
*/
for(var i=n; i>=0; i/=3) {}
// or
for(var i=0; i<n; i*=3) {}
Точно так же для сложности log7 n i должно уменьшаться на одну седьмую на каждой итерации.
for(var i=0; i<n; i*=7) {}
for(var i=n; i>=0; i/=7) {}
Теперь мы можем смешивать и сочетать наши основные сложности.
for(var i=0; i<n; i*=7) { // O(log7 n)
for(var j=0; j<n; j++) {} // O(n)
}
// Total complexity: O(n * log7 n)
На заметку: сложности одна внутри другой умножаются, где как одна на другую: доп.
Это весело, не правда ли. Давайте найдем еще несколько интересных способов выявления сложностей в следующих частях!
O (журнал журнала n):
‘i’ увеличивается на квадратный или уменьшается на квадратный корень:
// Complex examples:
for (var i=0; i<n; i++) {
for (var j=2; j<=n; j++){
j=j*j;
}
}
/*
* n=2; 2^1 2^(2^0) i: 0...1 j:2(1 time)
* n=4; 2^2 2^(2^1) i: 0...3 j:2,4 (2 times)
* n=16; 2^4 2^(2^2) i: 0...15 j:2,4,16 (3 times)
* n=256; 2^8 2^(2^3) i: 0...155 j:2,4,16,256 (4 times)
* n=65536; 2^16 2^(2^4) i: 0...65535 j:2,4,16,256,65536 (5 times)
*
* we can see that i's loop runs n times
* whereas j's loop runs k+1 times where
* 2^(2^k) = n
* log(2^(2^k)) = log n
* 2^k = log n
* log(2^k) = log log n
* k = log log n
*
* So total complexity of above program is: O(n (log (log n))) 🤯
*
* */
Вот где нам потребовалось немного времени и усилий. В данном примере основание журнала равно 2, для других оснований вы знаете, что делать. То же самое мы сделали для сложности log n в предыдущих примерах.
В следующих частях будет больше веселья!
Привет 🍻
