Идеи #1
Description
Мои упоротые идеи, которые не хочу потерять
https://github.com/hse-econ-data-science/dap_2021_spring/blob/main/sem06_dict/sem06_201.ipynb
Сюда во вторую задачку ещё вопросики:
-
За сколько работает len(x), где x строка? Ответ: O(1). Строка это объект, у которого есть атрибут длина. Он всегда посчитан и быстро вызывается. Так сделано во всех приличных языках программирования.
-
Если пишем в цикле
a = ' '
for item in x:
if ченить:
a += item
это оч плохо, потому что строка - изменяемый объект. Каждый раз при перезаписи он внутри памяти копируется полностью с первого символа. Эффективнее собрать всё это в массив, а потом сделать ' '.join( ). Там всё оптимальнее из-за того, что объект изменяемый и для него предусмотрена аллокация.
- Раскидать по варикам
O(1) len a[4:6] append (sum вроде атрибут тоже, но ето неточно, проверить)
O(n) index del pop remove in max min
O(k) extend
- Примеров разных сложностей без реализаций
- Жадные - коммивояжора O(n!), покрытие множества O(2^n)