Шаг 42.
Рекурсия на Python. Анализ времени выполнения рекурсивных алгоритмов. Предварительные математические соглашения. Верхняя и нижняя границы

    На этом шаге мы приведем основные свойства этих границ.

    Нижняя граница ⌊x⌋ вещественного числа х - это наибольшее целое число, не превосходящее х. Аналогично, верхняя граница ⌈х⌉ вещественного числа х - это наименьшее целое число, не меньшее х. Формально они могут быть определены как

    ⌊x⌋ = max {m ∈ Z | m ≤ х}, 
    ⌈х⌉ = min {m ∈ Z | m ≥ х},
где Z - множество целых чисел, а символ "|" читается как "такие, что". Следующий список включает несколько основных свойств нижних и верхних границ: где x - вещественное число, n - целое число, m - неотрицательное целое число и p - положительное целое число. Операция // вычисляет частное от целочисленного деления, а операция >> сдвигает целое число вправо на один двоичный разряд. Такие операции есть в языке Python и других языках программирования. Наконец, символ означает "тогда и только тогда".

    На следующем шаге мы вспомним тригонометрию.




Предыдущий шаг Содержание Следующий шаг