Доказательство основной теоремы для случая 1: как математически выводятся эти шаги?

Я читал книгу Томаса Х. Кормена, чтобы понять теорему «Доказательство Мастера». Однако я застрял в доказательстве случая 1. Пожалуйста, помогите мне понять математические доказательства с помощью более простого математического вывода шагов на следующем изображении:

введите здесь описание изображения

Спасибо


algorithm master-theorem
person user5005768Himadree    schedule 12.07.2016    source источник
comment
Используются две формулы: b^(log_b(a)) = a, а вторая — стандартная сумма геометрической прогрессии.   -  person Abhishek Bansal    schedule 12.07.2016
comment
@user5005768 Если пользователь ответил на ваш вопрос, пожалуйста, примите его ответ (Принятие ответов: как это работает?). Если нет, пожалуйста, укажите, что осталось без ответа, это действительно важная часть StackOverflow, большое спасибо.   -  person Zabuzard    schedule 27.07.2017

Ответы (1)


arrow_upward
1
arrow_downward

По первому вопросу:

b^{\log_b(a)} = a

(Разве у нас нет TeX в SO?)

Это потому, что логарифм по основанию b является обратным b^. Затем a / a = 1, поэтому остается только b^epsilon.

Второй и третий вопрос: это геометрический ряд, вы можете найти его здесь: https://en.wikipedia.org/wiki/Geometric_series#Formula
Для этого слагаемое b^epsilon должно быть между нулем и единицей (исключая), то есть |b^epsilon| < 1.

person Zabuzard    schedule 12.07.2016
comment
спасибо @Zabuza. Однако, не могли бы вы объяснить, что логарифм по основанию b является обратным b^ на примере? Благодарность - person user5005768Himadree; 12.07.2016
comment
Конечно. Стандартный логарифм, известный из школы, по основанию 10. Он является обратным 10^. Таким образом, log(10^5) = 5 и 10^(log(5)) = 5. Вы можете попробовать это с помощью калькулятора :) Хорошо, мы можем захотеть изменить основание школьного логарифма. Затем мы пишем log_b для логарифма по основанию b, это аналогично переворачивает b^. Например, log_e — это логарифм по основанию e, ln — его сокращение. Сам логарифм просто определяется как величина, обратная его основанию. Явной формулы нет, это так по определению. Вы можете прочитать: en.wikipedia.org/wiki/Logarithm :) - person Zabuzard; 12.07.2016