Вот проблема.
Я действительно смущен тем, что c равно части 0.5. На самом деле в целом я запутался, как logn может стать n^(0.5). Не мог бы я просто позволить c быть равным 100, что означало бы 100 < d, что приводит к использованию другого регистра? Что мне здесь не хватает?
Вы, конечно, могли установить c = 100 так, чтобы n^c было (очень, очень) грубой асимптотической верхней границей для log(n), но это дало бы вам ужасную и абсолютно бесполезную оценку времени выполнения T(n).
Это говорит вам следующее: каждая полиномиальная функция n^c растет быстрее, чем логарифм, независимо от того, насколько мала c, пока она остается положительной. Можно было бы взять c=0.0000000000001, вначале оно казалось бы смехотворно маленьким, но в какой-то момент оно стало бы больше, чем log(n), и расходилось бы в бесконечность гораздо быстрее, чем log(n). Поэтому, чтобы избавиться от члена n^2 log(n) и иметь возможность применить только полиномиальную версию Основной теоремы, вы ограничиваете логарифмический член чем-то, что растет достаточно медленно (но все же быстрее, чем log(n)). В этом примере достаточно n^c с c=0.5, но вы также можете взять c=10^{-10000} "просто для уверенности".
Затем вы применяете теорему Мастера и получаете разумную (и точную) асимптотическую верхнюю границу для вашего T(n).
log(n) термин. Вы хотите избавиться от него и получить какой-нибудь хороший (означает: асимптотически незначительный) многочлен вместо n^2 log(n). Таким образом, вы используете n^c с достаточно маленьким c в качестве верхней границы для log(n), так что второе слагаемое ограничено n^{2+c}. Затем вы продолжаете доказывать что-то о 8T([n/2]) + n^{2+c}, используя главную теорему.
- person Andrey Tyukin; 21.04.2015
