Шаг 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 и других языках программирования. Наконец, символ 
⇔ означает "тогда и только тогда".
   
На следующем шаге мы  вспомним тригонометрию.
Предыдущий шаг  Содержание
 
Содержание  Следующий шаг
 
Следующий шаг