写点什么

文心一言 VS chatgpt (15)-- 算法导论 3.2 4~5 题

  • 2023-05-07
    北京
  • 本文字数:689 字

    阅读完需:约 2 分钟

四、函数 多项式有界吗?函数 多项式有界吗?

文心一言:



chatgpt:


对于第一个问题,函数 是阶乘的形式,可以证明它是超多项式增长的,因此不是多项式有界的。


对于第二个问题,函数 的增长速度比 慢很多。虽然 不是多项式,但是它是多项式有界的,也就是说,存在一个多项式 和常数 ,使得当 足够大时,。这可以使用斯特林公式来证明。


五、如下两个函数中,哪一个渐进更大些:还是

文心一言:



chatgpt:


在这里,我们将 看作一个函数 ,分别表示对数幂函数的不同变形。


首先,我们知道对数幂函数增长非常缓慢,它们比多项式增长更慢,但比指数增长更快。因此,我们可以考虑使用渐进符号来比较这两个函数的上界关系。


由于 ,因此我们只需要比较 的增长速度即可。


根据定义,对数幂函数 表示在连续对数的情况下,最后得到的结果为 1 所需的次数。而对数幂函数 表示对数字 进行重复对数直到结果小于或等于 1 的次数。因此,$\lg^(\lg n)\log\lg(\lg^ n)$ 则表示连续应用反函数的次数。


由于反函数的增长速度要快于原函数,因此可以推断出 $\lg^(\lg n)\lg(\lg^ n)\lg^*(\lg n)$ 是渐进更大的函数。


因此,$\lg^(\lg n)\lg(\lg^ n)$。



发布于: 刚刚阅读数: 4
用户头像

公众号:福大大架构师每日一题 2021-02-15 加入

公众号:福大大架构师每日一题

评论

发布
暂无评论
文心一言 VS chatgpt (15)-- 算法导论3.2 4~5题_福大大_福大大架构师每日一题_InfoQ写作社区