Шаг 42.
Рекурсия на Python. Анализ времени выполнения рекурсивных алгоритмов. Предварительные математические соглашения. Верхняя и нижняя границы
На этом шаге мы приведем основные свойства этих границ.
Нижняя граница ⌊x⌋ вещественного числа х - это наибольшее целое число, не превосходящее х. Аналогично, верхняя граница ⌈х⌉ вещественного числа
х - это наименьшее целое число, не меньшее х. Формально они могут быть определены как
⌊x⌋ = max {m ∈ Z | m ≤ х},
⌈х⌉ = min {m ∈ Z | m ≥ х},
где
Z - множество целых чисел, а символ
"|" читается как "такие, что". Следующий список включает несколько основных свойств нижних и верхних границ:
- ⌊x⌋ ≤ x
- ⌈х⌉ ≥ x
- ⌊x + n⌋ = ⌊x⌋ + n
- ⌈х + n⌉ = ⌈х⌉ + n
- ⌊x⌋ + ⌊y⌋ ≤ ⌊x + y⌋
- ⌈х⌉ + ⌈y⌉ ≥ ⌈х + y⌉
- n = ⌊n/2⌋ + ⌈n/2⌉
- n - 2⌊n/2⌋ = 0 ⇔ n - четное
- n//2 = ⌊n/2⌋
- n>>m = ⌊n/2m⌋
- ⌊log10p⌋ + 1 = количество десятичных цифр
- ⌊log2p⌋ + 1 = количество двоичных цифр (битов)
где
x - вещественное число,
n - целое число,
m - неотрицательное целое число и
p - положительное целое число. Операция
// вычисляет частное от
целочисленного деления, а операция
>> сдвигает целое число вправо на один двоичный разряд. Такие операции есть в языке Python и других языках программирования. Наконец, символ
⇔ означает "тогда и только тогда".
На следующем шаге мы вспомним тригонометрию.
Предыдущий шаг
Содержание
Следующий шаг