Please enable JavaScript.

Coggle requires JavaScript to display documents.

Алгоритмы и структуры данных, Конспект по видосу, Как подойти к решению…

- - - - K - окно сглаживания. Это массив данных, который считает среднее арифметическое точек
      - N - длина входного списка
      - N * K - количество операций для обработки данных
      - При фиксированном N наивный алгоритм замедляется с увеличением K, а время работы второго (про оптимизированный алгритм) не изменяется.
        
        Идея, которая помогла оптимизировать функцию, называется «метод двух указателей». В алгоритме действительно есть два указателя: они задают начало и конец рассматриваемого интервала.
        
        Чтобы пересчитать среднее арифметическое:
        
        сначала изменяем его исходя из тех значений, на которые ссылаются указатели,
        
        а потом эти указатели смещаем.
        
        Эта простая и эффективная техника. Она часто применяется для решения задач на алгоритмических собеседованиях.
      - Оптимизированный наивный алгоритм считающий среднее скользящее. На примере задачи Скользящее среднее
      - Наивный алгоритм на примере задачи 2SUM. Дан массив числе и число X. Нужно найти в массиве два элемента сумма которых равна X.
        
        Начнём с наивного решения. Самое простое, что можно придумать, — перебрать все возможные пары блинов и для каждой пары проверить, равен ли её вес искомому.
        
        2 фишки https://contest.yandex.ru/contest/26365/problems/D/
        
        Оптимищация - Это снова метод двух указателей: один из них указывает на левый блин, а второй — на правый. На каждом шаге либо левый указатель сдвигается на один элемент вправо, либо правый — на один элемент влево. Указатели двигаются не в одном направлении, как в истории с окном сглаживания, а сходятся, поочерёдно двигаясь навстречу друг другу. Если в какой-то момент указатели встретятся — значит, искомая пара элементов в массиве отсутствует.
        
        Второй вариант: Если не хочется сортировать тяжёлые блины, можно использовать для решения этой задачи дополнительную память
        
        Например, позвать тренера, который наизусть помнит вес всех блинов в спортзале. В этом случае алгоритм будет такой: можно в любом порядке перебирать блины и, вытащив очередной (допустим, с весом AA), спрашивать: «А есть ли у вас блин с весом X - AX−A?». Когда консультант ответит «Да, есть такой» — можно оставить себе текущий блин, взять тот, что с весом X - AX−A, и пойти заниматься.
        
        Заплатить за хранение элементов в структуре данных поиска придётся, конечно, не деньгами, а оперативной памятью: в этом отличие нового алгоритма от двух предыдущих. Это решение очень быстрое, но не во всех ситуациях оно будет лучшим.
        
        В программировании это означает, что для решения задачи можно использовать вспомогательную структуру, которая называется «структура данных поиска».
      - Можем сказать, что скорость работы алгоритма в худшем случае пропорциональна размеру массива. На математическом языке ещё говорят: «Вычислительная сложность алгоритма линейно зависит от размера входных данных».
        
        Вычислительная сложность алгоритма. Обычно под этой фразой программисты понимают количество элементарных операций, которые будут совершены.
        
        Размер входных данных. Входные данные — то, что алгоритм получает на вход. В нашей задаче это массив numbers и переменная x. Размер входных данных примерно равен N.
        
        Линейная зависимость. Описывается формулой y = kx + by=kx+b. Например, если в комнате xx табуретов, то количество их ножек можно посчитать по формуле y = 4xy=4x. То есть количество ножек линейно зависит от количества табуретов. Если один из табуретов оказался трёхногим, зависимость всё ещё будет линейной: y = 4x - 1y=4x−1