关于复杂度
  • 板块学术版
  • 楼主bsdsdb
  • 当前回复15
  • 已保存回复15
  • 发布时间2024/8/6 21:42
  • 上次更新2024/8/6 23:40:16
查看原帖
关于复杂度
790188
bsdsdb楼主2024/8/6 21:42
  1. O(n2n)O(n^{2n}) 是否应该化简成 O(nn)O(n^n)

  2. 貌似所有的复杂度化简都满足 「当所有变量都趋近于无穷大时化简前和化简后的比都不为 00 且不为无穷」,例如 lim⁡n→+∞12n(n−1)n2=12\lim_{n\rightarrow+\infty}\dfrac{\frac{1}{2}n(n-1)}{n^2}=\dfrac{1}{2},lim⁡n→+∞∑i=1⌊n⌋1iln⁡(⌊n⌋)=1\lim_{n\rightarrow+\infty}\dfrac{\sum_{i=1}^{\lfloor n\rfloor}\frac{1}{i}}{\ln(\lfloor n\rfloor)}=1,但 lim⁡n→∞n2nnn=∞\lim_{n\rightarrow\infty}\dfrac{n^{2n}}{n^n}=\infty,还是说只有多项式复杂度满足那个性质

  3. O(∑i=1⌊n⌋1i)O(\sum_{i=1}^{\lfloor n\rfloor}\frac{1}{i}) 常被写成 O(log⁡n)O(\log n),此处的 log⁡\log 省略的底数是 22 还是 ee,还是说任何数都可以

2024/8/6 21:42
加载中...