是否存在函数$ f $，这样：$ f（n-k）\ ne \ theta（f（n））$ for for soming ancor $ k \ geq1 $？

Question

我在数据结构课程中的作业分配中遇到了以下问题：

“函数 $ f $ 存在，这样： $ f（nk）\ ne \ theta（f（n））$ 对于某些常量 $ k \ geq1 $ ？“

我认为没有这样的函数现有$ f $ ，但我不知道如何证明它（或者给出一个逆示例，如果存在）。

Answer 1

一个示例是 $ f（n）= 2 ^ {2 ^ n} $ 。现在， $ f（n-1）= 2 ^ {2 ^ {n-1}} $ ，我们有 $\ frac {f（n-1）} {f（n）}=frac {1} {2 ^ {2 ^ n - 2 ^ {n-1}}=frac {1} {2 ^ {2^ {n-1}}} $ 。因此， $ f（n-1）\ not \ in \ theta（f（n））$ 。在此示例中， $ k= 1 $ 。

Answer 2

tenderexample： $ f（n）= n！$ 作为 $ f（n）$ 是 $ n $ 时间大于 $ f（n-1）$ ，很清楚<跨度类=“数学集装箱”> $ f（n-1）\ neq \ theta（f（n））$ 。