提问人：David Jackson 提问时间：9/26/2020 更新时间：9/26/2020 访问量：160
加法的时间复杂度
Time Complexity of Addition
问：
我是计算时间复杂度的新手。我知道如果我们有常数项，我们就会忽略它，如果我们有方程，我们取项的最高幂，例如 x^3+2x^2+n 将有 O（n^3）。但是，当我们增加这些复杂性时，我们该怎么办？喜欢具体一点：O（n） + O（sqrt（n））的时间复杂度是多少。
答：
0赞
ItamarG
9/26/2020
#1
由于 O（Sqrt（n）） 实际上是 O（n^（1/2）） 并且 O（n） 是 O（n^1），因此按照这个逻辑，O（n） + O（sqrt（n）） <= 2*O（n） = O（n） 的复杂度
评论
0赞
dominicm00
9/26/2020
为了进一步扩展这一点，big-O 表示法只是提供了时间复杂度的上限。这意味着 O（n+sqrt（n））、O（n）、O（n^2） 等都是有效的。但是，您通常希望提供一个严格的上限，即。一个尽可能接近实际时间复杂度的方案。你把上限设得有多详细取决于你和上下文。在这种情况下，由于 sqrt（n） 在相当大的数字下比 n 小得多，因此 O（n） 将是表示它的最常见方式。
评论