Идеи

[FUlyankin]

Мои упоротые идеи, которые не хочу потерять

https://github.com/hse-econ-data-science/dap_2021_spring/blob/main/sem06_dict/sem06_201.ipynb

Сюда во вторую задачку ещё вопросики:

1. За сколько работает len(x), где x строка? Ответ: O(1). Строка это объект, у которого есть атрибут длина. Он всегда посчитан и быстро вызывается. Так сделано во всех приличных языках программирования.

2. Если пишем в цикле

a = ' ' 
for item in x:
   if ченить: 
       a += item

это оч плохо, потому что строка - изменяемый объект. Каждый раз при перезаписи он внутри памяти копируется полностью с первого символа. Эффективнее собрать всё это в массив, а потом сделать ' '.join( ). Там всё оптимальнее из-за того, что объект изменяемый и для него предусмотрена аллокация.

3. Раскидать по варикам

O(1)  len  a[4:6]  append  (sum вроде атрибут тоже, но ето неточно, проверить) 
O(n)  index  del  pop  remove  in  max  min 
O(k)  extend

4. Примеров разных сложностей без реализаций

• Жадные - коммивояжора O(n!), покрытие множества O(2^n)

[FUlyankin]

Кинуть новому ИП видосы: https://yandex.ru/yaintern/algorithm-training

[FUlyankin]

Интуицию за контестовые ограничения в стиле. Если N < 10^9, за O(N^2) точно не пройдет. Какой-нибудь C++ за секунду делает 10^9 элементарных операций, если операции сложнее - пробьёт. Python в сто раз медленнее. Отсюда прикидываем сложность решения.

[FUlyankin]

Упражнение про константы.

Что лучше? Алгоритм за 2 N log N или за 1000 N? N > 2^500. А будет ли у нас такой объём входа?

[FUlyankin]

Показать стресс-тестирование