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

✅1. Связанные списки изменяют свой размер динамически, то есть, добавлять или удалять элементы мы можем по мере необходимости без проблем поиска нужных ячеек памяти.

✅2. Отсюда вытекает следующий плюс со вставкой, или удалением элементов. Вставка или удаление элементы из середины занимает время O(1) (Очень эффективный алгоритм). Напоминаю, что O(1) - это постоянная сложность алгоритма, то есть размер входных данных нам не важен, сообщение я вам прикрепил, если забыли).

Теперь минусы:

❌1. Я вам уже сказал что в каждом элементе связанного списка хранится ссылка на следующий, следовательно, адрес нужного элемента мы получить не так уж и быстро. Проблема заключается в медленном доступе к индексу. Если в массиве мы изначально знаем адрес каждого элемента, то в связанном списке нам придется проходить от одного узла к другому, что занимает время O(n). Я уже говорил, что это постоянное время, проще говоря, нам придется пройтись по каждому элементу, чтобы найти нужный адрес элемента.

❌2. Второй основной минус вытекает из первого. Наши узлы - неупорядочены. Читать такие структуры данных - занятие не из быстрых. Их неупордоченность снижает эффективность использования кэш-памяти и может замедлять работу.

Теперь мы вполне можем выявить плюсы массивов и сравнить со списками.

1.✅ Конечно же это доступ к индексу. Мы изначально знаем адрес каждого элемента и легко можем обратиться к элементам по их индексу за время O(1). Это возможно благодаря тому, что элементы массива хранятся последовательно в памяти.

2.✅ Если со связанными списками есть проблема с использованием памяти, то у массивов затраты куда меньше, поскольку хранятся они последовательно в непрерывном блоке памяти.

Время выполнения основных операций и использование памяти.
‼️Могу пояснить, динамическая память на указатели в связанных списках - это значит, что на каждый указатель компьютер также выделяет память (у двусвязного списка будет два узла, на которые также будет выделена память), поэтому память динамически развивается.

Мы обязательно вернемся еще к этой теме, потому что это используется программистами повсеместно, как минимум)). Но я бы хотел еще поговорить об этом в практическом плане, показать примеры, но данная теория будет важна, как для меня, так и для вас.🧑‍💻

‼️Давайте подведем итоги‼️

Что лучше использовать? Связанные списки или Массивы? Массивы очень популярны, так как используют произвольный доступ (Это когда мы можем обратиться к нужному элементу по индексу. Например, будет у нас 5 элементов - можем обратиться к любому из них). Связанные списки поддерживают только последовательный доступ (Это когда мы можем читать элементы последовательно, начиная с первого. Пример тот же, есть 5 элементов, но, чтобы дойти до 5, нам нужно прочитать все перед ним и перейти по ссылкам к последнему пятому элементу). ⁉️

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

🧑‍💻Если же у нас случай, который требует постоянной вставки или удаления элементов в середине списка, динамическое изменение размера (размер структуры данных может изменяться в процессе работы программы), то смело используйте связанные списки!

✅Ссылки на материал с постов да и просто важные ссылки для вашего изучения. 💻

https://medium.com/nuances-of-programming/структуры-данных-и-алгоритмы-связный-список-6ae2625be22b - связаный список 🔗

https://medium.com/nuances-of-programming/структуры-данных-кольцевой-циклический-замкнутый-связный-список-93afae65157e - кольцевой связанный список 🖇

https://nuancesprog.ru/p/15493/ - двусвязный (двунаправленный) список 🧷

https://docs-python.ru/tutorial/operatsii-chislami-python/problemy-chisel-plavajuschej-zapjatoj/#float-error - проблема чисел с плавающей точкой с курса

https://struchkov.dev/blog/ru/floating-point-math/ - Точность чисел с плавающей запятой
https://stepik.org/course/58852/syllabus — КУРС, КОТОРЫЙ МЫ ПРОХОДИМ

🔗 Python: "Поколение Python": курс для начинающих.
🔗 Python: "Поколение Python": курс для начинающих (часть 2).
⚙️ Python (Базовые знания)
🖇 Алгоритмы
🌶 Machine learning
📁 Язык C
💲 Пост с навигацией на всякий
🐍 Разбор кода на Python
🧑‍💻ЕГЭ (Информатика): Решение задач на Python

✔️ Связанные списки и массивы💲

Достаточно большая тема, снизу будет представлена навигация по спискам и массивам... Таким лазурным цветом будем обозначать подтемы, к примеру, есть блок ❗️Алгоритмы❗️а ❗️Связанные списки и массивы❗️ достаточно большая подтема.

0️⃣ Вступление

1️⃣ Массивы

2️⃣ Основная проблема массивов

3️⃣ Резервирование места в массиве и минусы

4️⃣ Недостатки массивов ❌

5️⃣ Связные списки

6️⃣ Структура связного (однонаправленного) списка

7️⃣ Структура двусвязного (двунаправленного) списка

8️⃣ Структура кольцевого (циклического) связного списка

9️⃣ Кольцевой связанный список из односвязного.

1️⃣0️⃣ Кольцевой связанный список из двусвязного.

1️⃣1️⃣ Плюсы связных списков ✅

1️⃣2️⃣ Минусы связных списков ❌

1️⃣3️⃣ Плюсы массивов ✅

1️⃣4️⃣ Время выполнения основных операций и использование памяти 🕐

1️⃣5️⃣ Что лучше использовать❓

__________________________________

🟰Н А В И Г А Ц И Я🟰

🟰 В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰

‼️ Big(O) - это математическая нотация, которая описывает скорость работы алгоритма. Нужна она для понимания, какие алгоритмы работают медленно, а какие быстро..

Мы этой темы немного коснулись, ниже как обычно ссылки 🔗

0️⃣ Пояснение Big(O) и линейное время O(n)

1️⃣ Константная сложность O(1) и логарифмическое время O(log n)

2️⃣ Бинарный поиск и простой‼️

3️⃣ Снова линейное время ✔️

4️⃣ Квадратичная сложность и сортировка пузырьком✔️

5️⃣ Что такое Big(O) и зачем оно нужно? (обновленные посты)

6️⃣ Постоянное время (Константная сложность O(1))💲

7️⃣ Пример алгоритма со сложность O(1) на Python ❗️

8️⃣ Что такое Асимптотическая сложность алгоритма❓

9️⃣‼️ Что такое Логарифмическое время O(n log n), Бинарный поиск‼️

1️⃣0️⃣ Как найти средний индекс ❓

1️⃣1️⃣🌶Разбор кода бинарного поиска🌶

__________________________________

🟰Н А В И Г А Ц И Я🟰

🟰В Е Р Н У Т Ь С Я К А Л Г О Р И Т М А М🟰

Завтра, я думаю, можно посвятить еще постов этой теме, побольше расскажу про виды Big(O)

🧑‍💻Всем ку, хотел мы немного объединить темы по Big(O), чтобы у всех было понимание что это и с чем это едят. Но, в любом случае, я вам сделал пост про сложность алгоритмов и время выполнения, туда добавлю и сегодняшние посты.🖤

0️⃣🔗 Я уже говорил, что Big(O) это нотация, нужная для описания сложности алгоритмов. Она помогает нам описывать, насколько быстро работает алгоритм. Запись O(n) называется 'O - большое', ❗️n отвечает за количество операций. Такая запись отвечала бы, например, за проверку неотсортированного списка. Допустим, есть у нас список [0, 16, 22, 4, 17, 8]. Как вы видите, список не отсортирован, значит, если бы мы захотели найти какое то число в этом списке, то нам нужно пришлось бы пройтись по всем значениям этого списка.

1️⃣ Очень важный момент‼️. Запись Big(O) дает нам также представление о том, насколько наш алгоритм будет эффективен, по мере того, как будут увеличиваться входные данные. Пример все тот же: [0, 16, 22, 4, 17, 8].

🖇В нашем списке 6 элементов, а мы хотим найти, например, последний элемент - 8. Простым поиском, то есть, обычным перебором, мы это делали бы не так уж и долго, потому что элементов всего-навсего 6. А теперь представьте, что элементов в списке у нас не 6, а несколько тысяч) Навряд ли вам понравилось бы искать там какой-нибудь элемент...

🧑‍💻Начнем с постоянного времени O(1). Это константная сложность. Такая сложность возникает, когда наш алгоритм будет всегда иметь одинаковую производительность, независимо от размера вашего набора входных данных.

❓Помните наш пример списка [0, 16, 22, 4, 17, 8].?
Дак вот, мы с вами спокойно можем получить доступ к любому элементу по его индексу.

0 - 0
16 - 1
22 - 2
4 - 3
17 - 4
8 - 5

🔗Справа индексы элементов. Мы можем обратиться к любому из этих элементов по его индексу..
Проверка числа на четность или нечетность также является примером постоянного времени.

Йоу всем привет, ща будем разъ💀💀💀ывать биг (O)

ind = [1, 2, 3, 4, 5]
element = ind[3]
print(element)

🔗Вот вам пример работы такого алгоритма. ✅Ответ будет 4, потому что четверка имеет индекс 3, тут все логично) Мы получаем моментальный ответ, в этом и кайф константной сложности.🔝

‼️Кстати, со сложностью O(1), постоянной или константной сложностью (называйте как хотите), мы разобрались, дальше идет логарифмическое время...‼️

Теперь, разбираем логарифмическое время O(log n), примеры также будут, но не знаю, смогу ли разобрать их сегодня. Начинаем!

🔗 Для начала, введем такое понятие как ‼️Асимптотическая сложность алгоритма‼️ это оценка скорости роста времени работы алгоритма с увеличением размера входных данных, Она показывает, как время выполнения алгоритма или объем используемой памяти изменяется в зависимости от размера входных данных, когда этот размер становится очень большим. ✅ Проще говоря, найти из 1000 чисел загаданное, можно разными алгоритмами по-разному быстро, это и описывает наше новое понятие.

❗️Чтобы вы не путались, асимптотическая сложность описывает поведение алгоритма по времени в зависимости его входных данных, а Big(O) - это конкретный тип асимптотической сложности.

Теперь возвращаемся обратно к логарифмическому времени... Как раз у логарифмического времени асимптотическая сложность - O(log n) ❗️Это чисто для понимания, как это понятие будет употребляться в данном контексте❗️

Время выполнения такого алгоритма увеличивается логарифмически по мере роста размера входных данных. Щас вам объясню:

0️⃣ Вспомним сначала логарифмы, log2(8) = 3 ( Логарифм 8 по основанию 2 равен 3, потому что 2 возводим в 3 степень, первый шаг сделан )

1️⃣ Помните наш список [0, 16, 22, 4, 17, 8] пару постов назад? ‼️‼️Теперь отсортируем его [0, 4, 8, 16, 17, 22]. Зачем мы его отсортировали? Самый простой пример работы этого алгоритма - это бинарный поиск. Мы уже упоминали простой поиск, когда нам нужно перебрать все элементы, сравнивая их с нашей 'целью' (а проще сказать, с загаданным числом). пока не наткнемся на него. А бинарный поиск куда более эффективен... Суть такого поиска в постоянном делении отсортированного списка пополам, тем самым уменьшая количество возможных мест, где может находиться искомое число, но важно понимать, список для такого поиска должен быть отсортирован‼️‼️ Давайте на примере:

2️⃣ Берем наш отсортированный список [0, 4, 8, 16, 17, 22], он у нас уже отсортирован, теперь можно показать, как работает алгоритм на деле:

⭕️Допустим, ищем мы число 17. центральный элемент у нас 8. Кстати, подумайте почему 8, почему не 16, к примеру? Ведь список у нас состоит из четного количества элементов...Я отвечу чуть дальше в сообщении.

⭕️Дальше все еще проще, средний элемент 8, он сравнивается с 17, потому что это искомый элемент, в любом поиске с ним будет все сравниваться...Дак вот, 17 > 8, значит идем вправо по списку. 'Идем вправо' означает, что левую часть списка мы отбросили [0, 4, 8], 17 стоит правее середины, значит она нам не нужна...

✅Идем дальше, у нас остался список [16, 17, 22], средний элемент как раз 17!

https://t.me/itstudy_rus

Машинное обучение ☝🏻