Я читал книгу Томаса Х. Кормена, чтобы понять Доказательство теоремы Мастера. Однако я застрял в доказательстве case-1.please, помог мне понять математические доказательства путем более простого математического вывода шагов на следующем изображении:Доказательство теоремы Мастера для случая 1: как эти шаги математически получены?
Благодаря
Для первого вопроса:
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.
спасибо @ Zabuza.However, может, пожалуйста, объяснить ** логарифм к базе b является обратным b^** с примером? спасибо – user5005768
Конечно. Стандартный логарифм, известный из школы, относится к базе 10. Он является инверсией '10 ^'. Таким образом, log (10^5) = 5' и '10^(log (5)) = 5'. Вы можете попробовать его с калькулятором :) Хорошо, мы можем захотеть изменить базу * школьного логарифма *. Затем мы записываем 'log_b' для логарифма в базу' b', он аналогичным образом меняет значение 'b ^'. Например, 'log_e' является логарифмом базы' e', 'ln' аббревиатурой. Сам логарифм просто определяется как обратный к его базе. Не существует явной формулы, поэтому для определения. Вы можете прочитать: https://en.wikipedia.org/wiki/Logarithm :) – Zabuza
Используются две формулы: b^(log_b (a)) = a, а вторая - стандартная сумма геометрической прогрессии. –
@ user5005768 Если пользователь ответил на ваш вопрос, пожалуйста, также ** примите ** его ответ ([Принятие ответов: как это работает?] (Https://meta.stackexchange.com/questions/5234/how-does-accepting- ан-ответ-работа)). Если не, пожалуйста, укажите, что остается без ответа, это действительно важная часть StackOverflow, спасибо вам большое. – Zabuza