Владстон Феррейра Фило

Когда два события не могут произойти одновременно, они несовместные, или взаимоисключающие. Если вам нужно подсчитать вероятность любого из нескольких несовместных событий, просто просуммируйте их индивидуальные вероятности.

Ваш замок защищен пятью башнями. Каждая имеет 20 %-ную вероятность поразить захватчика, прежде чем он достигнет ворот. Каковы шансы остановить его?

Вероятность поразить врага равна 0,2 + 0,2 + 0,2 + 0,2 + 0,2 = 1, или 100 %, верно? Неверно! Никогда не суммируйте вероятности независимых событий, не совершайте распространенной ошибки. Вместо этого используйте взаимодополняющие события дважды следующим образом.

• 20 %-ный шанс поразить врага — взаимодополняющий для 80 %-го шанса промахнуться. Вероятность того, что не попадут все башни, составляет 0,85 ≈ 0,33

Мы говорим о рекурсии, когда функция делегирует работу своим клонам.

Существует специальная форма записи, которая обозначает классы роста временных затрат: нотация «О большое

Рис. 2.3. Различные обозначения роста сложности, которые часто можно увидеть внутри

Работа, на которую алгоритму с квадратично растущей стоимостью потребуются годы, может быть выполнена за минуты алгоритмом со сложностью O(n log n). Вот почему при создании систем, обрабатывающих очень большие объемы данных, необходимо делать анализ временной сложности

Кнут Д. Искусство программирования. Т. 1 (The Art of Compu­ter Programming

Если видишь хороший ход — ищи ход получше

Если требуется максимальная производительность, то можно избежать этих дополнительных издержек, переписав рекурсивный алгоритм в чисто итеративной форме

Итеративная стратегия состоит в использовании циклов (например, for и while) для повторения процесса до тех пор, пока не окажется соблюдено некое условие