‼️ 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

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

Начнем пост с того, почему все-таки выбрали 8 как середину списка [0, 4, 8, 16, 17, 22]⁉️

Вообще, чтобы найти средний индекс массива,‼️нужно начальный индекс сложить с конечным и поделить все на 2‼️

✅СРЕДНИЙ ИНДЕКС = (НАЧАЛЬНЫЙ + КОНЕЧНЫЙ) / 2

В нашем случае, начальный - 0, конечный 5, пятерку делим на 2 и получаем 2 (как индекс, округлять ничего не нужно).

🐍 Разбор кода (Python)

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

Итак:

list = [1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27]  # Отсортированный массив
aim = 23  #Элемент, который мы ищем, вы можете брать любой

left = 0 #Начальный индекс
right = len(list) - 1 #Конечный индекс

#Пока левая граница не превысит правую:
while left <= right:
    mid = (left + right) // 2  # Находим середину массива
    mid_value = list[mid]  # Элемент в середине массива

    if mid_value == aim:
        print(f"Элемент найден на индексе: {mid}")
        break  # Элемент найден, выходим из цикла
    
    elif mid_value < aim:
        left = mid + 1  # Если искомый элемент больше, сдвигаем левую границу вправо на 1
    
    else:
        right = mid - 1  # Если искомый элемент меньше, сдвигаем правую границу влево на 1
else:
    print("Элемент не найден")

0️⃣ У нас имеется отсортированный массив из 14 элементов, ❗️наше искомое число на 2 строчке, пусть будет 23❗️, хотя вы можете поставить любое..

1️⃣ Обозначаем границы, left - это начальный индекс [0], right - конечный индекс - 1 [Это будет 13] (Вычитаем 1, потому что длинна нашего списка 14, а вот индексация начинается с 0, следовательно, чтобы получить 13 индексов, вычитаем 1).

2️⃣ Создаем цикл while. который работает до тех пор, пока пока левая граница не превысит правую⁉️. Как я вам уже говорил, суть бинарного поиска в постоянно делении отсортированного списка. Дак вот, пока цикл работает, еще есть часть массива, где есть наше число.

3️⃣ Находим средний элемент массива: 🟰 mid = (left + right) // 2 🟰 Это получается 0 + 13 // 2 = 6 (Как раз выше писал, как найти средний индекс 🔝).
Дальше, 🟰 mid_value = list[mid] 🟰 Переменная mid_value будет равна 13. ⭕️

‼️То есть, переменная mid будет равна 6 (это средний индекс), а переменной mid_value находим элемент этого среднего индекса, это 13.‼️

4️⃣ Бывает такое, что средний элемент и будет искомым числом, первым условием это и проверяем.

Дальше, проверяем условие:
Если средний элемент меньше искомого, то left (Начальный индекс[0] = средний[6] + 1, и того получаем 7)⭕️

Первый сдвиг бинарного поиска ⬇️

5️⃣ Теперь смотрите в чем прикол. ‼️‼️Переменная left (начальный индекс) у нас теперь равен значению 7, конечный все также 13. То есть, наш диапазон для поиска элемента 23 сдвинулся вправо. Просто представьте, что список обрезали с 0 индекса по 7 (не включительно).‼️‼️

6️⃣ Мы вернулись в начало, теперь переменная mid равна 10⭕️ (Она была равна 6, а сейчас мы снова складываем начальный индекс[7] с конечным[13] и делим на 2 = 10) . Средний индекс равен 10, а вот переменная mid_value теперь равна 21, так как этот элемент как раз находится под индексом 10. ⭕️

7️⃣‼️Дальше также приходим к elif mid_value < aim:
left = mid + 1


Второй сдвиг бинарного поиска⏬

Если у нас mid_value[21] < aim[23], снова сдвигаем границу вправо, получаем left = 11, теперь у нас список состоит из элементов [23, 25, 27].

8️⃣ Снова находим средний индекс, это 12, затем элемент под этим индексом - 25. ⭕️

9️⃣ Не if не elif не срабатывают, срабатывает лишь последий оператор else. Переменная right[13] = mid[11] - 1. (Получаем right = 11)⭕️

Третий сдвиг бинарного поиска⏬

1️⃣0️⃣ Наконец! Теперь у нас обе переменные равны 11 (left, right). В последний раз находим средний индекс это 11, а элемент как раз 23! Наш искомый!

‼️Первое условие срабатывает и наш средний элемент как раз равен 23. ‼️

‼️Может показаться, что тут куча ненужной инфы, но такой алгоритм нужно было разобрать, поэтому я сделал это объемно‼️
‼️Возле некоторых переменных я писал квадратные скобочки, к примеру, как здесь right[13] = mid[11] - 1, внутри этих скобок находятся нынешние значения этих переменных, чтобы вы не путались и не искали выше‼️
✅Если вам есть, что добавить, пишите в комменты✅

Гайс, завтра постараюсь сделать пост, пока что ведутся визуальные изменения канала🧑‍💻. Половина канала уже изменена, так что ждать постов осталось немного. Также завтра будет оформлена навигация по числам типа float (а точнее проблема этих чисел).

⭕️‼️ Курс по Python никуда не денется, сегодня будет пост за долгое время, но, параллельно этому будем изучать новую науку 🔗

⭕️ Эти дни я занимался визуалом канала, вы можете это заметить по измененной навигации и измененным постам с самого начала создания канала.

⭕️ Теперь к каждому посту будет прилагаться код для собственной проверки.

🧑‍💻Всем удачного использования канала