Алгоритмы и структуры данных - webkoth/style-guide-php-laravel GitHub Wiki

Конспект из книг по алгоритмам и структурам данных

Computer Science для программиста самоучки Алгоритмы. Самый краткий и понятный курс. Грокаем алгоритмы машинного обучения ChatGPT

Как улучшить алгоритмическое мышление

Улучшение алгоритмического мышления может быть достигнуто через систематическое развитие навыков и подходов к решению проблем. Вот несколько пунктов, которые могут помочь улучшить ваше алгоритмическое мышление:

1. Понимание основных концепций: Основой для развития алгоритмического мышления является понимание основных концепций алгоритмов и структур данных. Изучайте различные типы алгоритмов и структур данных, их свойства, принципы работы и производительность. Это поможет вам выбирать подходящие алгоритмы и структуры данных для решения задач.

2. Решение задач на алгоритмы: Регулярно практикуйтесь в решении задач, связанных с алгоритмами и структурами данных. Начните с простых задач и постепенно переходите к более сложным. Разберите каждую задачу на составные части, определите входные данные и ожидаемый результат, разработайте план решения и реализуйте алгоритм. Затем проверьте и протестируйте свое решение.

3. Анализ сложности: Изучите методы анализа сложности алгоритмов. Разберитесь с большой "O" нотацией и оценкой временной и пространственной сложности алгоритмов. Умение оценивать сложность поможет вам выбирать наиболее эффективные алгоритмы для решения задач.

4. Практика абстрактного мышления: Развивайте свои навыки абстрактного мышления, способность видеть общие паттерны и алгоритмические подходы к решению проблем. Определите ключевые шаги или операции, которые могут быть использованы для решения различных задач, и применяйте их в новых контекстах.

5. Изучение различных алгоритмических подходов: Изучите различные алгоритмические подходы, такие как жадные алгоритмы, динамическое программирование, разделяй и властвуй и т.д. Понимание различных подходов поможет вам выбирать наиболее подходящий для решения конкретных задач.

6. Работа в команде: Участие в коллективной разработке алгоритмов и структур данных поможет вам изучить различные методы и подходы. Обсуждайте и анализируйте различные решения, обменивайтесь идеями и опытом с другими разработчиками.

7. Чтение и исследование: Постоянно читайте книги, статьи и ресурсы, связанные с алгоритмами и структурами данных. Изучайте новые исследования и разработки в этой области. Это поможет вам расширить свои знания и оставаться в курсе последних тенденций и лучших практи

• Алгоритмы и структуры данных являются основными компонентами программирования и компьютерной науки. Они используются для организации и обработки данных с целью решения задач и оптимизации работы компьютерных программ.

• Алгоритм - это последовательность инструкций или операций, предназначенных для выполнения определенной задачи. Алгоритмы можно рассматривать как "рецепты" для выполнения определенных действий. Они описывают шаги, необходимые для достижения желаемого результата. Алгоритмы могут быть представлены в виде блок-схем, псевдокода или программного кода.

• Структуры данных - это способы организации и хранения данных в компьютере. Они позволяют эффективно обрабатывать и получать доступ к данным. Каждая структура данных имеет свои особенности и применяется для определенных задач. Например, массивы, списки, стеки, очереди, деревья и графы - это различные типы структур данных.

• Основная цель алгоритмов и структур данных - улучшить производительность программ и оптимизировать использование ресурсов компьютера. Хорошие алгоритмы и эффективные структуры данных могут сократить время выполнения программы, уменьшить объем используемой памяти и улучшить общую производительность системы.

• Изучение алгоритмов и структур данных позволяет разработчикам понимать, как выбрать и применять наиболее подходящие методы для решения конкретных задач. Это ключевые навыки в области программирования и компьютерной науки, которые помогают создавать эффективные и оптимизированные программы.

Основные разделы алгоритмов и структур данных

1. Анализ алгоритмов: Изучение производительности алгоритмов в терминах времени выполнения и использования ресурсов. Включает в себя оценку сложности алгоритмов, большую "O" нотацию и амортизационный анализ.

2. Сортировка и поиск: Различные алгоритмы сортировки (например, сортировка пузырьком, сортировка вставками, сортировка слиянием, быстрая сортировка) и алгоритмы поиска (например, линейный поиск, бинарный поиск).

3. Структуры данных: Различные типы структур данных, такие как массивы, списки, стеки, очереди, деревья, графы и хеш-таблицы. Включает в себя операции, связанные с каждой структурой данных, их реализацию и анализ производительности.

4. Рекурсия: Понятие рекурсии и рекурсивных алгоритмов, включая примеры таких алгоритмов, например, факториал и вычисление чисел Фибоначчи.

5. Динамическое программирование: Метод решения сложных задач, разбивая их на более простые подзадачи и сохраняя результаты для повторного использования. Включает в себя понятия, такие как оптимальная подструктура и перекрытие подзадач.

6. Графы: Теория графов и алгоритмы, связанные с работой с графами, такие как обходы графов (например, обход в глубину, обход в ширину), поиск минимального остовного дерева (например, алгоритм Прима, алгоритм Краскала) и кратчайший путь (например, алгоритм Дейкстры, алгоритм Беллмана-Форда).

7. Хеш-функции и хеш-таблицы: Понятие хеш-функций и их использование для эффективного поиска и вставки в хеш-таблицы.

8. Параллельные алгоритмы: Разработка алгоритмов, которые могут выполняться параллельно на множестве процессоров или ядер.

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

Более сложные алгоритмы

9. Генетические алгоритмы: Моделирование эволюционных процессов с использованием алгоритмов, вдохновленных биологической эволюцией. Они используются для решения оптимизационных задач и поиска наилучших решений.

10. Графические алгоритмы: Алгоритмы для обработки графических данных, такие как алгоритмы растровой графики (например, алгоритм Брезенхема для рисования линий) и алгоритмы обработки изображений (например, фильтры для улучшения качества изображений).

11. Алгоритмы машинного обучения: Алгоритмы, которые позволяют компьютерным системам "обучаться" на основе данных и принимать решения или делать прогнозы. Примеры включают в себя алгоритмы классификации (например, метод k-ближайших соседей) и алгоритмы кластеризации (например, алгоритм k-средних).

12. Алгоритмы глубокого обучения: Специализированные алгоритмы машинного обучения, использующие нейронные сети с множеством слоев для обработки сложных данных, таких как изображения, звук или текст.

13. Комбинаторика: Изучение комбинаторных структур и алгоритмов, связанных с подсчетом, перечислением и оптимизацией комбинаторных объектов, таких как перестановки, сочетания и разбиения.

14. Алгоритмы криптографии: Алгоритмы, используемые для шифрования и дешифрования данных, а также для обеспечения безопасности информации. Примеры включают в себя алгоритмы шифрования RSA и AES.

15. Алгоритмы оптимизации: Алгоритмы, которые помогают находить наилучшие решения в оптимизационных задачах, таких как задачи линейного программирования или задачи коммивояжера.

Это лишь некоторые из множества тем и понятий, связанных с алгоритмами и структурами данных. Изучение этих концепций поможет вам лучше понять и применять различные методы и подходы в программировании и разработке программ.

Advanced

1. Алгоритмы на графах: Это включает в себя алгоритмы поиска кратчайшего пути во взвешенных и невзвешенных графах (например, алгоритм Дейкстры, алгоритм Беллмана-Форда), алгоритмы поиска потоковых путей (например, алгоритм Форда-Фалкерсона), алгоритмы поиска минимального остовного дерева (например, алгоритм Прима, алгоритм Краскала) и алгоритмы поиска сильно связанных компонентов (например, алгоритм Косарайю).

2. Алгоритмы сжатия данных: Разработка алгоритмов для сжатия данных с минимальной потерей информации. Примеры включают в себя алгоритм Хаффмана, алгоритм Лемпела-Зива-Велча и алгоритм сжатия JPEG.

3. Алгоритмы параллельных и распределенных вычислений: Исследование алгоритмов, которые могут быть эффективно выполнены на множестве процессоров или узлов в распределенной среде. Это включает в себя алгоритмы сортировки, алгоритмы графов и алгоритмы обработки данных.

4. Теория сложности вычислений: Исследование верхних и нижних оценок сложности алгоритмов и задач. Включает в себя классы сложности, такие как P, NP, NP-полные задачи и различные методы доказательства сложности задач.

5. Квантовые алгоритмы: Разработка алгоритмов, которые могут быть выполнены на квантовых компьютерах и обеспечивают преимущества по сравнению с классическими алгоритмами. Примеры включают в себя алгоритм Шора для факторизации больших чисел и алгоритм Гровера для поиска в неупорядоченных базах данных.

6. Алгоритмы машинного обучения глубокого обучения: Разработка и исследование сложных алгоритмов глубокого обучения, которые позволяют нейронным сетям обрабатывать большие объемы данных и решать сложные задачи, такие как распознавание образов или обработка естественного языка.

Это лишь некоторые из самых продвинутых и сложных тем, связанных с алгоритмами и структурами данных. Изучение этих концепций требует глубоких знаний и понимания основных концепций алгоритмов и структур данных, а также дополнительного изучения и исследования в этих областях.

---

Введение в алгоритмы

1. Что такое алгоритм ?

Алгоритм — это последовательность шагов, которая решает задачу.

1. Количество шагов должно быть конечным. Алгоритмы не могут рабо-тать вечно (программа может работать до тех пор, пока работает компьютер, на котором она запущена; но такая программа была бы не реализацией алгоритма, а просто вычислительным процессом).
2. Шаги должны быть точными, чтобы их можно было выполнять без дву-смысленностей.
3. Алгоритм может работать с каким-нибудь вводом.
4. У алгоритма есть какой-то вывод; в этом весь его смысл: вернуть что-то в качестве результата.
5. Алгоритм должен быть эффективным. У человека должна быть возмож-ность выполнить каждый его шаг за разумное время с помощью ручкии листа бумаги.

При работе с алгоритмами недостаточно просто показать возможность выполнить какую-либо задачу. Мы преследуем практические цели, поэтому наши алгоритмы должны выполнять свою работу хорошо. В этом заключается принципиальное отличие между алгоритмами и ма- тематикой. На заре развития информатики большинство компьютерщиков были математиками, и в компьютерных науках используется много матема- тических концепций, но это не математическая дисциплина. Математик хо- чет доказать какое-то тождество; специалист в области информатики хочет применить это тождество на практике.

Время выполнения алгоритма — это количество необходимого ва- шему компьютеру времени, чтобы выполнить алгоритм, написанный на языке программирования.

Поскольку на время выполнения алгоритма влияет множество различных пере- менных, таких как вычислительные мощности компьютера и язык программи- рования, оценка данного параметра — не очень эффективный способ сравнения двух алгоритмов. Вместо этого специалисты в области информатики сравнивают алгоритмы по количеству шагов, которые требуются для их выполнения.

for i in range(1, 6):
	print(i)

f(n) = 5

count = 0
for i in range(1, 6):
	print(i)
	count += i

f(n) = 1 + 5 + 5 = 11

1 -> count = 0 -> присвоение 5 -> print(i) -> пять иттераций цикла (вывод) 5 -> count += i -> пять иттераций цикла (инкремент)

f(n) = 1 + 2n

n - размер задачи

Математическое обозначение: T(n) = 1 + 2n

Необходимо знать об алгоритме — не точное, а, скорее, приблизительное количество шагов, которое потребуется при увеличении n.

Нотация «O большое» — это математическое обозначение, описывающее, как по мере роста n возрастают требования алгоритма к времени и объему памяти.

Программисты используют нотацию «О большое» для создания функции поряд- ка величины T(n).

Порядок величины — тип объекта в системе классификации, в которой каждый тип во много раз больше или меньше предыдущего.

В функции порядка величины вы используете ту часть T(n), которая преобладает в уравнении, и игнорируете все остальное. Часть T(n), преобладающая в уравнении, — это порядок величины алгоритма. Ниже представлены общепринятые классификации порядка величины для нотации «О большое»: от наилучшего (наиболее эффективного) до наихудшего (наименее эффективного):

• постоянное время;
• логарифмическое время;
• линейное время;
• линейно-логарифмическое время;
• квадратичное время;
• кубическое время;
• экспоненциальное время.

Каждый порядок величины описывает временн ю сложность алгоритма. Временн я сложность — это максимальное количество шагов, требующихся алгоритму для завершения по мере увеличения n.

Постоянное время

Наиболее эффективным порядком величины является постоянная временная сложность. Алгоритм выполняется за постоянное время, когда ему требуется одно и то же количество шагов вне зависимости от объема задачи. Нотация «О большое» для постоянной сложности — О(1).

Допустим, у вас онлайн-магазин книг и каждый день вы дарите книгу первому покупателю. Вы храните своих покупателей в списке customers. Алгоритм может выглядеть следующим образом:

free_books = customers[0]

А равенство T(n) выглядит так: T(n) = 1

Логарифмическое время

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

Логарифмический алгоритм в нотации «О большое» выражается как О(log n).

[!info] Что такое логарифм По большому счёту, логарифм — это просто перевёрнутая степень. Рассмотрим выражение 23 = 8. В нём:2 — основание степени; 3 — показатель степени; 8 — результат возведения в степень. У возведения в степень существует два обратных выражения. В одном мы ищем основание (это извлечение корня), в другом — показатель (это логарифмирование).Таким образом, выражение 23 = 8 можно превратить в log2 8 = 3. Закрепляем знания: логарифм — это число, в которое нужно возвести 2 (основание степени), чтобы получить 8 (результат возведения в степень). Форма записи неинтуитивна, и поначалу можно легко спутать основание со степенью. Чтобы избежать этого, можно использовать следующее правило: Основание у логарифма, как и у возведения в степень, находится внизу. Чтобы лучше запомнить структуру записи, посмотрите на эти выражения и постарайтесь понять их смысл:

Линейное время

Следующий по эффективности тип алгоритма — тот, который выполняется за линейное время. Такой алгоритм растет пропорционально росту размера задачи. Линейный алгоритм в нотации «О большое» выражается как О(n)

free_book = False
customers = ["Lexi", "Britney", "Danny", "Bobbi", "Chris"]
for customer in customers:
	if customer[0] == 'B':
	print(customer)

В линейном алгоритме по мере роста n количество шагов алгоритма увеличи- вается на то же количество, что и n.

Линейно-логарифмическое время

Алгоритм, выполняющийся за линейно-логарифмическое время, растет как сочетание (умножение) логарифмических и линейных временн х сложностей. Например, линейно-логарифмический алгоритм может вычислять операцию О(log n) n раз. В нотации «О большое» линейно-логарифмический алгоритм выражается как О(n log n). Линейно-логарифмические алгоритмы часто разделяют набор данных на меньшие части и каждую из них обрабатывают по отдельности. Например, большинство наиболее эффективных алгоритмов сортировки,с которыми вы познакомитесь далее, такие как сортировка слиянием, являются линейно-логарифмическими.

Линейно-логарифмическое время в контексте алгоритмов означает, что время выполнения алгоритма растет линейно с увеличением размера входных данных, умноженное на логарифм этого размера. Такое время работы алгоритма является более эффективным, чем линейное время, но менее эффективным, чем логарифмическое время. Алгоритмы с линейно-логарифмическим временем, такие как QuickSort или MergeSort, обычно имеют хорошую производительность при обработке больших объемов данных.

Квадратичное время

Алгоритм выполняется за квадратичное время, когда его произ- водительность прямо пропорциональна размеру задачи в квадрате. В нотации «О большое» квадратичный алгоритм выражается как О(n**2).

Квадратичное время в контексте алгоритмов означает, что время выполнения алгоритма растет пропорционально квадрату размера входных данных. Если размер входных данных увеличивается вдвое, время выполнения алгоритма увеличивается примерно вчетверо. Алгоритмы с квадратичным временем, такие как Bubble Sort или Selection Sort, обычно имеют неэффективную производительность при обработке больших объемов данных. Использование таких алгоритмов может привести к значительному увеличению времени выполнения и затратам ресурсов.

numbers = [1, 2, 3, 4, 5]
for i in numbers:
	for j in numbers:
		x = i * j
		print(x)

В данном случае n — это размер вашего списка numbers. Уравнение для временной сложности алгоритма следующее:

f(n) = 1 + n * n * (1 + 1)

В этом уравнении (1 + 1) является результатом умножения и вывода. Вы повторяете умножение и вывод n * n раз с двумя вложенными циклами for.

Можно упростить уравнение: f(n) = 1 + (1 + 1) * n**2

Что идентично следующему: f(n) = 1 + 2 * n**2

Как вы уже могли догадаться, преобладает часть уравнения n2, поэтому в нотации «О большое» равенство будет таким: O(n) = n2

Кубическое время

Алгоритм выполняется за кубическое время, когда производительность прямо пропорциональна размеру задачи в кубе. В нотации «О большое» вы выражаете кубический алгоритм как О(n**3). Алгоритм с кубической сложностью похож на квадратичный, только n возводится в третью степень, а не во вторую.

numbers = [1, 2, 3, 4, 5]
for i in numbers:
	for j in numbers:
		for h in numbers:
			x = i + j + h
			print(x)

Уравнение для этого алгоритма следующее:

f(n) = 1 + n * n * n * (1 + 1)

Или же: f(n) = 1 + 2 * n**3

Как и в алгоритме с квадратичной сложностью, наиболее важная часть данного уравнения — n3, которая растет так быстро, что остальная часть уравнения, даже та, что включает в себя n2, становится нерелевантной.

Таким образом, в нотации «О большое» кубическая сложность выглядит так:

O(n) = n**3

Два вложенных цикла свидетельствуют о квадратичной временн й сложности, а три вложенных цикла, выполняемых от 0 до n, — признак алгоритма с кубическим временем. Весьма вероятно, что вы столкнетесь с кубической временной сложностью, если ваша работа связана с data science или статистикой. И квадратичная, и кубическая временн е сложности представляют собой частные случаи полиномиальной временн й сложности. Алгоритм, который выполняется за полиномиальное время, вычисляется как О(n**а), где а = 2 для квадратичного времени и а = 3 для кубического времени. При создании алгоритма, как правило, пытаются избежать полиномиального масштабирования, потому что алгоритм может работать очень медленно при увеличении n. Иногда избежать полиномиального масштабирования не получается, но в таком случае вы можете успокаивать себя тем, что полиномиальная сложность — еще не самый худший вариант.

Экспоненциальное время

Алгоритм, который выполняется за экспоненциальное время, содержит константу, увеличенную до размеров задачи. Другими словами, алгоритму с экспоненциальным временем для завершения требуется с шагов, возведенных в степень n. Нотация «О большое» для экспоненциального времени равна О(с**n), где с — это константа. Значение константы не играет роли. Важно лишь то, что n находится в экспоненте.

pin = '931'
n = len(pin)
pin = 931
for i in range(10**n):
	if i == pin:
		print(i)

Поисковые алгоритмы

Линейный поиск

В линейном поиске вы перебираете каждый элемент в наборе данных и сопоставляете его с целевым числом. Если ваше сравнение находит совпадение — число находится в списке. Если алгоритм завершается, не найдя совпадения, — числа в списке нет.

def linear_search(a_list, n):
	for i in a_list:
		if i == n:
			return True
	return False

a_list = [1, 8, 32, 91, 5, 15, 9, 100, 3]
print(linear_search(a_list, 91))

Когда следует использовать линейный поиск

Временн я сложность линейного поиска — О(n). Если у вас список из десяти элементов, в худшем случае сценария алгоритму потребуется десять шагов.

В среднем линейному поиску требуется n/2 шагов. Вам следует рассмотреть вариант использования линейного поиска, если ваши данные не отсортированы. Отсортированные данные — данные, упорядоченные определенным образом.

print(44 in [0, 125, 78, 44, 46, 59])

Двоичный поиск

Двоичный (бинарный) поиск — еще один, более быстрый алгоритм для поиска в списке чисел. Однако его нельзя применять для любого набора данных, потому что он работает только с отсортированными данными.

def binary_search(a_list, n):
    first = 0
    last = len(a_list) - 1
    
    while last >= first:
        mid = (first + last) // 2
        if a_list[mid] == n:
            return True
        else:
            if n < a_list[mid]:
                last = mid - 1
            else:
                first = mid + 1
    return False
    

print(binary_search([1, 2, 3, 14, 45, 48, 89], 89))

Когда следует использовать двоичный поиск

Двоичный поиск имеет временн ю сложность О(log n). Он более эффективен, чем линейный, так как не нужно просматривать весь список. Вместо этого вы можете исключать из поиска целые сегменты списка. Эффективность двоичного поиска особенно заметна, когда речь идет о работе с большими объемами данных. Например, когда вы ищете в списке, состоящем из миллиона чисел, с линейным поиском может потребоваться миллион шагов для завершения, а с логарифмическим двоичным — только 20.

Алгоритмы сортировки

Не нужно применять классические алгоритмы сортировки, которые мы здесь рассматриваем (за исключением редких случаев), потому что в современных языках программирования, таких как Python, имеются встроенные функции, работающие быстрее. Однако изучение нескольких классических алгоритмов сортировки поможет вам лучше разобраться с временн й сложностью и по- знакомит с важными концепциями, знание которых пригодится и в решении других задач.

Пузырьковая сортировка

Пузырьковая сортировка — это алгоритм сортировки, при котором вы перебираете список чисел, сравнивая каждое число с последующим, и пере- ставляете их, если они идут не по порядку. Программисты называют такую сортировку пузырьковой, потому что наибольшие числа «всплывают» в конце списка, а наименьшие перемещаются в начало списка по мере выполнения алгоритма.

def bubble_sort(a_list):
    list_length = len(a_list) - 1
    for i in range(list_length):
        for j in range(list_length):
            if a_list[j] > a_list[j + 1]:
                a_list[j], a_list[j + 1] = a_list[j + 1], a_list[j]
    return a_list

print(bubble_sort([5, 1, 78, 456, 89, 15, 4, 68, 89]))

Когда следует использовать пузырьковую сортировку

В рассмотренной нами реализации пузырьковой сортировки алгоритм сорти- ровал числа, но ее (как и любую другую сортировку) можно использовать и для сортировки строк. Например, вам нужно изменить пузырьковую сортировку так, чтобы она отсортировала строки в алфавитном порядке по первой букве каждой строки. Преимущество пузырьковой сортировки в простоте ее применения, поэтому она хорошо подходит тем, кто только начинает изучать алгоритмы сортировки. Поскольку данная сортировка основана на двух вложенных циклах for, ее временн я сложность равна О(n**2). Хотя она может быть эффективна для малого набора данных, но для большого набора данных ее эффективность снижается.