Помогите, пожалуйста, найти определение "скорости роста последовательности"
С определением встретился тут (друг поступал, а мне просто задачки понравились):
http://mit.spbau.ru/files/20100424_sobes_cs.pdf
Скажите только определение, а решить интересно самому.
Спасибо заранее.
Полная версия: Скорость роста последовательности > Разное
Ну, точных определений Вы скорее всего не найдёте. Потому что "скорость роста" есть некий сленг, хотя и очевидный всем, кто имеет дело с пределами.
Если есть две растущие куда-нибудь последовательности a(n) и b(n), то про них говорят, что скорость их роста одинакова, если верхний предел их отношения не превосходит некоторой положительной постоянной, и нижний предел не меньше некоторой положительной постоянной. Т.е. отношение a(n)/b(n) отделено от нуля и ограничено сверху начиная с некоторого n.
Когда говорят про определение скорости роста последовательности, имеют в виду сравнение её с некоторой "канонической" растущей последовательностью, чья скорость роста всем понятна: например, со степенной, показательной или логарифмически растущей последовательностью. Так, последовательность (n+7)^5 растёт как n^5, (3+25/n^2)^n - как 3^n, и т.п. "Оценить скорость роста" рекуррентно заданной последовательности T(n) - значит, предъявить две такие явным образом заданные последовательности a(n) <= b(n), что верхний предел отношения T(n)/b(n) не больше единицы, а нижний предел отношения T(n)/a(n) не меньше единицы. Тогда можно будет сказать, что T(n) растёт не быстрее b(n), но не медленнее a(n). Лучше всего, если эти последовательности совпадут - тогда скорость роста (в данном случае её называют асимптотикой) T(n) найдена точно, или если a(n) и b(n) отличаются на константу.
Если есть две растущие куда-нибудь последовательности a(n) и b(n), то про них говорят, что скорость их роста одинакова, если верхний предел их отношения не превосходит некоторой положительной постоянной, и нижний предел не меньше некоторой положительной постоянной. Т.е. отношение a(n)/b(n) отделено от нуля и ограничено сверху начиная с некоторого n.
Когда говорят про определение скорости роста последовательности, имеют в виду сравнение её с некоторой "канонической" растущей последовательностью, чья скорость роста всем понятна: например, со степенной, показательной или логарифмически растущей последовательностью. Так, последовательность (n+7)^5 растёт как n^5, (3+25/n^2)^n - как 3^n, и т.п. "Оценить скорость роста" рекуррентно заданной последовательности T(n) - значит, предъявить две такие явным образом заданные последовательности a(n) <= b(n), что верхний предел отношения T(n)/b(n) не больше единицы, а нижний предел отношения T(n)/a(n) не меньше единицы. Тогда можно будет сказать, что T(n) растёт не быстрее b(n), но не медленнее a(n). Лучше всего, если эти последовательности совпадут - тогда скорость роста (в данном случае её называют асимптотикой) T(n) найдена точно, или если a(n) и b(n) отличаются на константу.
Цитата(Vahappaday @ 15.7.2012, 19:16) 
Помогите, пожалуйста, найти определение "скорости роста последовательности"
Если имеем дело с функцией y(x), то скорость ее изменения (убывания, возрастания) определяется производной y'(x). Функция растет, где y'(x)>0
Может и здесь так сделать?
Например последовательность задается общей формулой
T(n)=n=1,2,3,4,5..
Скорость T'(n)=1>0 т.е. разность между последующим и предыдущем слагаемым равна 1. Все вроде логично
Н-да... Про "очевидный всем, кто" было сказано явно поспешно.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.