一个不连续的函数如何分析增长速率或者说算法复杂度比如这样一个函数,定义域为自然数1~N,值为N能整除的2的最大次幂,比如f(8)=2^3=8,f(20)=2^2=4,f(21)=2^0=1.这样一个函数的增长速率如何比较,是

Question

一个不连续的函数如何分析增长速率或者说算法复杂度
比如这样一个函数,定义域为自然数1~N,值为N能整除的2的最大次幂,比如f(8)=2^3=8,f(20)=2^2=4,f(21)=2^0=1.这样一个函数的增长速率如何比较,是在O(n)和O(logn)之间么?

Answer 1

大O记号用于上界的表示,用O(...)做下界没有意义
你这里 f(n)=O(n),下界只能得到f(n)=ω(1),不要指望f(n)=ω(log n),因为f在所有奇数点的取值都是1,根本就不是无穷大量
另外,一般来讲函数连续不连续问题不大,只定义在整数上的函数总是连续函数,你所谓的不连续只不过是不能解析延拓而已.在渐进分析的时候多用用不等式的技术,少依赖初等函数的运算.